String question

Here is an interesting string question

Given 2 strings x(smaller length)and y(larger length). Return t/f if you can change x to y. Both contain only 'a' and 'b'. Operations to perform:
1) Append 'a' at the end of x
2) Reverse x and append 'b' at the end

A naive solution and improved one can be found here.

import time
def x_to_y(x, y):
    i = len(x)
    if x!=y[:i]:return False
    while len(x)<len(y):
        if y[i]=='a':x += 'a'
        else:
            if x!=x[::-1]:return False
            x += 'b'
    return True


def x_to_y2(x, y):
    i = len(x)
    if x!=y[:i]:return False
    b_idx = [i for i,c in enumerate(x) if c=='b']
    b_idx_set = set(b_idx)
    while len(x)<len(y):
        if y[i]=='a':x += 'a'
        else:
            b_idx.append(len(x))
            b_idx_set.add(len(x))
            for idx in b_idx:
                if idx>(len(x)+1//2):
                    break
                else:
                    symmetrical_idx = len(x)-(idx+1)
                    if symmetrical_idx not in b_idx_set:return False
            x += 'b'
    return True

if __name__ == "__main__":
    x = "abb"
    y = "abababaa"
    print("first one is: ", x_to_y(x, y))
    print("second one is:", x_to_y2(x, y))
    x = "a"
    y = "a"*10000
    print("first one is: ", x_to_y(x, y))
    print("second one is:", x_to_y2(x, y))
    x = "a"
    N = 1000000
    y = 'a'*N+'b'+'a'*N+'b'+'a'*N+'b'
    begin = time.time()
    print(x_to_y(x, y))
    print("first one is: ", x_to_y(x, y))
    print('time used for naive', time.time()-begin)
    begin = time.time()
    print("second one is:", x_to_y2(x, y))
    print('time used for the second algorithm', time.time()-begin)

The output is below:

first one is:  False
second one is: False
first one is:  True
second one is: True
True
first one is:  True
time used for naive 6.0135498046875
second one is: True
time used for the second algorithm 2.355654239654541

From the output, we can see that the second one is faster than the first one based on the test case.

The second solution has a bug, we only check the left half index of b, we didn’ t check the right half. The checking of right half should be added to garuantee correctness.

C++ code for from wisp

#include <string>
#include <iostream>
using namespace std;
bool solve(string x, string y){
    int i=0, j=y.size()-1;
    bool dir = 0;
    while(j-i+1 > x.size()){
        auto& end = dir?i:j;
        int delta = dir?1:-1;
        switch(y[end]){
            case 'a': end += delta; break;
            case 'b': end += delta; dir = !dir; break;
        }
    }
    for(int ii=0,jj=(dir?j:i);ii<x.size();ii++,(dir?--jj:++jj))
        if(x[ii]!=y[jj])
            return false;
    return true;
}
int main(){
    cout << solve("ab", "bab") << endl;
    cout << solve("ba", "bab") << endl;
    cout << solve("ba", "baa") << endl;
}