11

2つの文字列がありますが、一方がもう一方の回転バージョンであるかどうかを確認するにはどうすればよいですか？

For Example : hello --- lohel

簡単な解決策の1つは、concatenating最初にそれ自体で文字列を作成し、もう1つがsubstring連結バージョンであるかどうかを確認することです。

それに対する他の解決策はありますか？

多分使えるかなcircular linked list？しかし、私は解決策にたどり着くことができません。

4

11 に答える 11

10

簡単な解決策の1つは、それらを連結し、もう1つが連結バージョンのサブストリングであるかどうかを確認することです。

最初の文字列をそれ自体と連結することを意味していると思います。次に、他の文字列がその連結のサブ文字列であるかどうかを確認します。

これは機能し、実際には連結なしで実行できます。文字列検索アルゴリズムを使用して、最初の文字列の2番目の文字列を検索し、最後に到達したら、最初にループバックします。

たとえば、Boyer-Mooreを使用すると、全体的なアルゴリズムはO（n）になります。

于 2012-08-19T21:37:01.077 に答える
6

連結する必要はまったくありません。

まず、長さを確認してください。それらが異なる場合は、falseを返します。

次に、ソースの最初の文字から最後の文字まで増分するインデックスを使用します。宛先がインデックスから最後までのすべての文字で始まり、インデックスの前のすべての文字で終わるかどうかを確認します。いつでもこれがtrueの場合、trueを返します。

それ以外の場合は、falseを返します。

編集：

Pythonでの実装：

def isrot(src, dest):
  # Make sure they have the same size
  if len(src) != len(dest):
    return False

  # Rotate through the letters in src
  for ix in range(len(src)):
    # Compare the end of src with the beginning of dest
    # and the beginning of src with the end of dest
    if dest.startswith(src[ix:]) and dest.endswith(src[:ix]):
      return True

  return False

print isrot('hello', 'lohel')
print isrot('hello', 'lohell')
print isrot('hello', 'hello')
print isrot('hello', 'lohe')
于 2012-08-19T17:28:17.230 に答える
3

各文字列の辞書式順序で最小の文字列回転を計算し、それらが等しいかどうかをテストできます。

最小回転の計算はO（n）です。

これは、テストする文字列がたくさんある場合に適しています。これは、最小回転を前処理ステップとして適用してから、標準のハッシュテーブルを使用して回転した文字列を格納できるためです。

于 2012-08-19T17:32:39.020 に答える
3

些細なO（min（n、m）^ 2）アルゴリズム：（n-S1の長さ、m-S2の長さ）

isRotated（S1、S2）：

if (S1.length != S2.length)
    return false
for i : 0 to n-1
    res = true
    index = i
    for j : 0 to n-1
       if S1[j] != S2[index]
           res = false
           break
       index = (index+1)%n
    if res == true
        return true
return false

編集：

説明 -

長さmとnの2つの文字列S1とS2は、m == nであり、インデックス0 <= j <= n-1（S1 = S [j] S [j + 1] .. S [n-1] S [0] ...S[j-1]。

したがって、上記のアルゴリズムでは、長さが等しいかどうか、およびそのようなインデックスが存在するかどうかを確認します。

于 2012-08-19T17:36:47.897 に答える
1

非常に簡単な解決策は、単語の1つをn回回転させることです。ここで、nは単語の長さです。これらのローテーションのそれぞれについて、結果が他の単語と同じであるかどうかを確認します。

于 2012-08-19T17:27:20.143 に答える
1

あなたはO(n)時間とO(1)空間でそれを行うことができます：

def is_rot(u, v):
    n, i, j = len(u), 0, 0
    if n != len(v):
        return False
    while i < n and j < n:
        k = 1
        while k <= n and u[(i + k) % n] == v[(j + k) % n]:
            k += 1
        if k > n:
            return True
        if u[(i + k) % n] > v[(j + k) % n]:
            i += k
        else:
            j += k
    return False

詳細については、ここで私の答えを参照してください。

于 2015-12-01T16:07:39.467 に答える
0

Javaでのシンプルなソリューション。反復や連結の必要はありません。

private static boolean isSubString(String first, String second){
        int firstIndex = second.indexOf(first.charAt(0));
        if(first.length() == second.length() && firstIndex > -1){

            if(first.equalsIgnoreCase(second))
                return true;

            int finalPos = second.length() - firstIndex ; 
            return second.charAt(0) == first.charAt(finalPos)
            && first.substring(finalPos).equals(second.subSequence(0, firstIndex));
        }
        return false;

    }

テストケース：

String first = "bottle";
String second = "tlebot";

論理：

最初の文字列の最初の文字を取得し、2番目の文字列のインデックスを見つけます。見つかったインデックスを使用して秒の長さを減算し、0の2番目の最初の文字が2番目の長さと見つかったインデックスの長さの差の文字と同じであり、これら2つの文字間の部分文字列が同じであるかどうかを確認します。

于 2013-10-23T00:31:28.633 に答える
0

別のPython実装（連結なし）は効率的ではありませんが、O（n）であり、コメントがある場合はそれを楽しみにしています。

2つの文字列s1とs2があると仮定します。

明らかに、s1とs2が回転である場合、s1にはs2の2つのサブ文字列が存在し、それらの合計は文字列の長さになります。

問題は、s2の文字がs1の文字と一致するたびに、s2のインデックスをインクリメントするパーティションを見つけることです。

def is_rotation(s1, s2):
    if len(s1) != len(s2):
        return False
    n = len(s1)
    if n == 0: return True

    j = 0
    for i in range(n):
        if s2[j] == s1[i]:
            j += 1
    return (j > 0 and s1[:n - j] == s2[j:] and s1[n - j:] == s2[:j])

2番目の条件は、s2に対してインクリメントされたカウンターがサブ文字列に一致することを確認することだけです。

于 2014-05-11T08:01:11.770 に答える
0

input1 = "hello" input2 = "llohe" input3 = "lohel"（input3は特殊なケースです）

input 1とinput2の長さが同じでない場合は0を返します。iとjをそれぞれinput1とinput2を指す2つのインデックスとし、countをinput1.lengthに初期化します。falseに設定されているisRotatedというフラグを設定します

while（count！= 0）{

input1のキャラクターがinput2と一致する場合

  1. iとjをインクリメント
  2. カウントのデクリメント

キャラクターが一致しない場合

  1. isRotated = trueの場合（回転後も不一致があることを意味します）、中断します。
  2. それ以外の場合は、不一致があるため、jを0にリセットします。例えば：

以下のコードを見つけて、私が考慮しなかった可能性のある他の組み合わせで失敗した場合はお知らせください。

    public boolean isRotation(String input1, String input2) {
    boolean isRotated = false;
    int i = 0, j = 0, count = input1.length();

    if (input1.length() != input2.length())
        return false;

    while (count != 0) {

        if (i == input1.length() && !isRotated) {
            isRotated = true;
            i = 0;
        }

        if (input1.charAt(i) == input2.charAt(j)) {
            i++;
            j++;
            count--;
        }

        else {
            if (isRotated) {
                break;
            }
            if (i == input1.length() - 1 && !isRotated) {
                isRotated = true;
            }
            if (i < input1.length()) {
                j = 0;
                count = input1.length();

            }
            /* To handle the duplicates. This is the special case.
             * This occurs when input1 contains two duplicate elements placed side-by-side as "ll" in "hello" while 
             * they may not be side-by-side in input2 such as "lohel" but are still valid rotations. 
             Eg: "hello" "lohel"
            */
            if (input1.charAt(i) == input2.charAt(j)) {
                i--;
            }
            i++;
        }
    }
    if (count == 0)
        return true;
    return false;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(new StringRotation().isRotation("harry potter",
            "terharry pot"));
    System.out.println(new StringRotation().isRotation("hello", "llohe"));
    System.out.println(new StringRotation().isRotation("hello", "lohell"));
    System.out.println(new StringRotation().isRotation("hello", "hello"));
    System.out.println(new StringRotation().isRotation("hello", "lohe"));
}
于 2014-09-21T22:43:26.420 に答える
0

O（n）で問題を解決する

void isSubstring(string& s1, string& s2)
{
    if(s1.length() != s2.length())
        cout<<"Not rotation string"<<endl;
    else
    {
        int firstI=0, secondI=0;
        int len = s1.length();

        while( firstI < len )
        {
            if(s1[firstI%len] == s2[0] && s1[(firstI+1) %len] == s2[1])
                break;

            firstI = (firstI+1)%len;
        }

        int len2 = s2.length(); 
        int i=0;
        bool isSubString = true; 
        while(i < len2)
        {
            if(s1[firstI%len] != s2[i])
            {
                isSubString = false;
                break;
            }
            i++;
        }

        if(isSubString)
            cout<<"Is Rotation String"<<endl;
        else
            cout<<"Is not a rotation string"<<endl;
    }
}
于 2016-05-25T17:06:20.180 に答える
-1 
    String source = "avaraavar";
    String dest =   "ravaraava";

    System.out.println();
    if(source.length()!=dest.length())
        try {
            throw (new IOException());
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

    int i = 0;
    int j = 0;
    int totalcount=0;
    while(true)
    {
        i=i%source.length();    
        if(source.charAt(i)==dest.charAt(j))
        {   
            System.out.println("i="+i+" , j = "+j);
            System.out.println(source.charAt(i)+"=="+dest.charAt(j));
            i++;
            j++;
            totalcount++;   
        }
        else
        {
            System.out.println("i="+i+" , j = "+j);
            System.out.println(source.charAt(i)+"!="+dest.charAt(j));
            i++;
            totalcount++;   
            j=0;
        }
        if(j==source.length())
        {
            System.out.println("Yes its a rotation");
            break;
        }
        if(totalcount >(2*source.length())-1)
        {
            System.out.println("No its a rotation");
            break;
        }
    }
于 2016-06-02T13:26:05.583 に答える