Comparing two different solutions to a quiz
<p>I've been going through a course on CS on Udemy, and got a quiz to solve.</p>

<p>Here's what is says:</p>

<blockquote>
  <p>Define a procedure, find_last, that takes as input two strings, a
  search string and a target string, and returns the last position in
  the search string where the target string appears, or -1 if there are
  no occurrences.</p>
  
  <p><strong>Example</strong>: <code>find_last('aaaa', 'a')</code> returns 3</p>
</blockquote>

<p>The first solution is mine, the last is theirs. My question is, in what ways is theirs better than mine, and how could I think next time when solving this kind of a problem, so I would come to a solution faster and better. (I've spent at least 45 min thinking of a solution). </p>

<pre><code>def find_last(s, t):
    some = s.find(t)
    i = some
    while s.find(t, i) != -1:
        some=s.find(t, i)
        i=i+1
   return some

def find_last(s,t):
    last_pos = -1
    while True:
        pos = s.find(t, last_pos+1)
        if pos==-1:
            return last_pos
        last_pos = pos
</code></pre>

<p>Here are the examples:</p>

<pre><code>print find_last('aaaa', 'a') # returns 3
print find_last('aaaaa', 'aa') # returns 3
print find_last('aaaa', 'b') # returns -1
print find_last("111111111", "1") # returns 8
print find_last("222222222", "") # returns 9
print find_last("", "3") # returns -1
print find_last("", "") # returns 0
</code></pre>

<p>I think <strong>the main idea of the course is to learn algorithms</strong> and this exercise is  good to start with (<em>regardless if the solution is not the most efficient way to resolve such problems in a current programming language</em>). So, their solution is better because they 'jump' during iteration, and you steps by 1, after you found index of first occurrence of <code>t</code>. I will try to explain with simple example:</p>

<p>You have got a string <code>s = 'abbbabbba'</code> and you need to find <code>'a'</code>. When you use your function, let it be <code>fun_last_1(s, 'a')</code>:</p>

<pre><code>def find_last_1(s, t):
    some = s.find(t)           # some = 0
    i = some                   # i = 0
    while s.find(t, i) != -1:  # ok
        some=s.find(t, i)      # you again start from 0 (some = 0) ???
        i=i+1                  # and from here you steps by 1
                               # put print(i) in this row 
    return some                # in total you will have 9 iterations
</code></pre>

<p>you will need 9 iterations to achieve final result in this case. While they need only 4, lets add a print statement inside their loop:</p>

<pre><code>def find_last_2(s,t):
    last_pos = -1                   
    while True:                     
        pos = s.find(t, last_pos+1) 
        print(pos)                   # add print here
        if pos==-1:                 
            return last_pos         
        last_pos = pos               # here they jumps

&gt;&gt;&gt; find_last_2(s,'a')
0
4
8
-1

# and of course it will return 8
</code></pre>

<p>You can also add this debuggy <code>print()</code> inside the loop in your function and compare:</p>

<pre><code>&gt;&gt;&gt; find_last_1(s, 'a')
1
2
3
4
5
6
7
8
9

# and of course it will return 8
</code></pre>

<p>Hope this will help you to understand the difference.</p>

python algorithm