首页 > 代码库 > 飞范超神之作

飞范超神之作

技术分享

解题思路:每次去掉目标字符串的末尾一个字符,这边要设置一个方向变量,这样就可以用双指针法来代替翻转字符串的操作,时间复杂度O(target.length())。

string canObtain(string src, string tar){
    if(src.length() > tar.length()) return "Impossible";
    int left = 0 , right = tar.length() - 1 ,front_to_end = 1;
    while(right - left + 1 != src.length()){
        if(front_to_end){
            if(tar[right] == A)right--;
            else {
                front_to_end = 0;
                right--;
            }
        }
        else {
            if(tar[left] == A)left++;
            else {
                front_to_end = 1;
                left++;
            }
        }
    }
    if(!front_to_end) reverse(src.begin(), src.end());
    return src =http://www.mamicode.com/= tar.substr(left, src.length()) ? "Possible" : "Impossible";
}

 

飞范超神之作