トップ > coding interview > 文字列の回転

文字列の回転

coding interview coding interview-配列と文字列

問題

２つの文字列str1, str2が与えられた時に、str2がstr1を回転させたものであるか調べる。 例えば

  • str1 = "apple"
  • str2 = "pplea"

ならtrue である。

考え方

回転させたものなら str2 + str2としたものの中にstr1が含まれるはずである。 ただし、str1.length()==str2.length()の時だけ調べれば良いことに注意する。

str1がstrに含まれているか調べるには、 str1の１文字目がstrの中に出てくるか調べて、そこからstr1.length()分の文字列str[i:i+str1.length()]がstr1と等しいか判定する。 注意点として、何回かstr1の１文字目が出ることがありうるので、いきなりfalseを返さないようにする。

計算量

str1の長さをN, str2の長さをMとする。ただし、ちゃんと判定を行うのはN=Mの時だけ。 含まれているかの判定を最大(2M-N)回行う。等しいかの判定に必要な計算量がO(1)であれば、時間計算量はO(N)

コード例

C++

#include<iostream>
#include<string>
using namespace std;

bool isSubstring(string str1, string str2){
    //-- str1がstr2の中に含まれるか判定する。
    int i, j, n1, n2;
    // str1の１文字目がstr2にある場所探す
    n1 = str1.length();
    n2 = str2.length();
    for(i=0; i<n2-n1; i++){
        if(str1.substr(0, 1)==str2.substr(i, 1)){
            if(str1==str2.substr(i, n1)){
                return true;
            }
        }
    }
    return false;
}
bool isRotation(string str1, string str2){
    string str;
    if(str1.length()==str2.length()){
        str = str2 + str2;
        return isSubstring(str1, str);
    }
    return false;
}

int main(void){
    bool flg;
    string str1, str2;
    str1 = "apple";
    str2 = "pplea";
    cout << "文字列1は " << str1 << endl;
    cout << "文字列2は " << str2 << endl;
    flg = isRotation(str1, str2);
    cout << "回転させたものか? " << boolalpha << flg << endl;
    return 0;
}

参考

問題は 世界で闘うプログラミング力を鍛える本 | マイナビブックス から