有 2 个字符串，我们如何检查一个是否是另一个的旋转版本？
For Example : hello --- lohel
一个简单的解决方案是通过concatenating第一个字符串本身并检查另一个是否是substring串联版本的 a 。
还有其他解决方案吗？
我想知道我们是否可以使用circular linked list也许？但我无法得出解决方案。
问问题
13065 次
11 回答
10
一个简单的解决方案是连接它们并检查另一个是否是连接版本的子字符串。
我假设您的意思是将第一个字符串与其自身连接，然后检查另一个是否是该连接的子字符串。
这将起作用，实际上可以在没有任何连接的情况下完成。只需使用任何字符串搜索算法在第一个字符串中搜索第二个字符串，当您到达末尾时，循环回到开头。
例如，使用Boyer-Moore的整体算法将是 O(n)。
于 2012-08-19T21:37:01.077 回答
6
根本不需要串联。
首先，检查长度。如果它们不同，则返回 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 的长度）
旋转（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 的字符串 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
一个非常直接的解决方案是将其中一个单词旋转 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
input1="hello" input2="llohe" input3="lohel"（input3 是特殊情况）
如果输入 1 和输入 2 的长度不同，则返回 0。设 i 和 j 分别为指向 input1 和 input2 的两个索引，并将计数初始化为 input1.length。有一个名为 isRotated 的标志设置为 false
而（计数！= 0）{
当 input1 的字符匹配 input2
- 增加 i & j
- 递减计数
如果字符不匹配
- 如果 isRotated = true（这意味着即使在旋转之后也存在不匹配）所以 break;
- 否则将 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
另一个python实现（没有连接）虽然效率不高，但它是O（n），如果有的话期待评论。
假设有两个字符串 s1 和 s2。
显然，如果 s1 和 s2 是旋转的，那么在 s1 中存在 s2 的两个子串，它们的总和就是串的长度。
问题是每当 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])
第二个和条件只是为了确保为 s2 增加的计数器是子字符串匹配。
于 2014-05-11T08:01:11.770 回答
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";
逻辑：
取第一个字符串的第一个字符，在第二个字符串中找到索引。用找到的索引减去第二个的长度，检查第二个在 0 处的第一个字符是否与第二个的长度不同处的字符相同，找到的索引和这两个字符之间的子字符串是否相同。
于 2013-10-23T00:31:28.633 回答
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 回答