How to iterate from the end to the start in a string? (In constant space and linear time complexity)

Question

Created Feb ’21

Replies 5

Boosts 0

Participants 2

There is an index called endIndex in a string which is the index after a last element of a string. So, I can iterate through a string from start like this:

Code Block Swiftvar index = s.startIndex
while index != s.endIndex {
    index = s.index(after: index)
}

But I want to iterate from the end. Is there an elegant way to do it? Thanks in advance!

Boost

Answer 1

Claude31 OP

Feb ’21

Accepted Answer

Did you try this:

Code Block var index = s.endIndex
while index != s.startIndex {
    index = s.index(before: index)
    print(s[index])     // Just to see
}

1

Answer 2

Deeus OP

Feb ’21

it is fail in case when string is empty, because index != s.startIndex is true and when s.index(before: index) it is out of boundary

0

Answer 3

Deeus OP

Feb ’21

Sorry it is actually correct because s.startIndex equals to s.endIndex when string is Empty. I didn't know that! THANK YOU

0

Answer 4

Claude31 OP

Feb ’21

I tested in playground, did not get a crash with a "" String.
In fact, in that case s.endIndex == s.startIndex, so we don't enter the loop.

I tested direct and reverse exploration (100 iterations on a string of about 40 chars)

Elapsed time Reversed: 0.1168900728225708 seconds
Elapsed time direct: 0.33927905559539795 seconds

Twice as fast in reverse…

1

Answer 5

Deeus OP

Feb ’21

It turns out that reversed works in O(1), it does not allocate memorry!!!!!! So maybe this is reason why it is fast

0