java - 面试题: Check if one string is a rotation of other string

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开， visit the help center寻求指导。

关闭 11年前.

锁定。这个问题及其答案是 locked因为这个问题是题外话，但具有历史意义。它目前不接受新的答案或交互。

我的一个 friend 今天在面试软件开发人员的职位时被问到以下问题:

给定两个字符串 s1和 s2您将如何检查 s1是 s2 的旋转版本?

示例:

如果 s1 = "stackoverflow"那么以下是它的一些旋转版本:

"tackoverflows"
"ackoverflowst"
"overflowstack"

其中 "stackoverflwo" 不是旋转版本。

他给出的答案是:

Take s2 and find the longest prefix that is a sub string of s1, that will give you the point of rotation. Once you find that point, break s2 at that point to get s2a and s2b, then just check if concatenate(s2a,s2b) == s1

对我和我的 friend 来说，这似乎是一个很好的解决方案。但面试官不这么认为。他要求一个更简单的解决方案。请在 Java/C/C++ 中告诉我你将如何做到这一点来帮助我。 ?

提前致谢。

Answer 1

首先确保 s1 和 s2 的长度相同。然后检查 s2 是否是 s1 与 s1 连接的子字符串:

algorithm checkRotation(string s1, string s2) 
  if( len(s1) != len(s2))
    return false
  if( substring(s2,concat(s1,s1))
    return true
  return false
end

在 Java 中:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}