面试问题：检查一个字符串是否其他字符串的旋转 [英] Interview question: Check if one string is a rotation of other string

问题描述

我的一个朋友被提出以下问题今天在接受采访时对软件开发人员的位置：

由于两个字符串 S1 和 S2 你将如何检查是否 S1 是一个旋转 S2 ？

的 示例：的

如果 S1 =计算器那么下面是它的一些旋转版本：

 tackoverflows
ackoverflowst
overflowstack
 

在这里为stackoverflwo为的不的旋转后的版本。

他给的答案是：结果

  

以 S2 并找到最长的preFIX即 S1 的子字符串，这将使你旋转点。一旦你找到那个点，突破 S2 在这一点上要获得 S2A 和 S2B ，然后就检查连击（S2A，S2B）== S1

它看起来像一个很好的解决了我和我的朋友。但是面试官却不以为然。他要了一个简单的解决方案。请帮我告诉你怎么会在的Java / C / C ++ ？

做到这一点

先谢谢了。

解决方案

首先确保 S1 和 S2 是的相同的长度。然后检查是否 S2 是一个子 S1 与 S1 ：

 算法checkRotation（字符串S1，S2线）
  如果（LEN（S1）！= LEN（S2））
    返回false
  如果（子（S2，CONCAT（S1，S1））
    返回true
  返回false
结束
 

在Java的：

 布尔isRotation（字符串S1，S2的字符串）{
    返回（s1.length（）== s2.length（））及＆放大器; （（S1 + S1）.indexOf（S2）= -1！）;
}
 

A friend of mine was asked the following question today at interview for the position of software developer:

Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?

Example:

If s1 = "stackoverflow" then the following are some of its rotated versions:

"tackoverflows"
"ackoverflowst"
"overflowstack"

where as "stackoverflwo" is not a rotated version.

The answer he gave was:

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

It looks like a good solution to me and my friend. But the interviewer thought otherwise. He asked for a simpler solution. Please help me by telling how would you do this in Java/C/C++ ?

Thanks in advance.

解决方案

First make sure s1 and s2 are of the same length. Then check to see if s2 is a substring of s1 concatenated with 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

In Java:

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

这篇关于面试问题：检查一个字符串是否其他字符串的旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！