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

Question

我的一个 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);
}