字符串问题:判断两个字符是否互为旋转词

时间:2022-04-22 15:48:01

题目

  如果一个字符串 str, 把字符串 str 前面任意的部分挪到后面形成的字符串叫做 str 的旋转词。比如 str=“12345”,str 的旋转词有 "12345"、“23451”、“34512”、“45123” 和 “51234”.给定两个字符串 a 和 b, 请判断 a 和 b 是否互为旋转词。

 【举例

  a="cdab", b="abcd", 返回 true

  a="1ab2", b="ab12", 返回 false

  a="2ab1", b="ab12", 返回 true

要求

  如果 a 和 b 的长度不一样,那么 a 和 b 不互为旋转词,直接返回 false。当 a 和 b 长度一样,都为 N 时,要求解法的时间复杂度为 O(N)。

解答

  如果 a 和 b 的长度不一样,那么 a 和 b 不互为旋转词,直接返回 false。如果 a 和 b 长度一样,则先生成一个字符串 b2 = b + b, 然后判断 b2 中是否包含 a, 若包含则返回 true, 不包含则返回 false。

  具体实现见如下代码中的 isRotation 方法:

 1 public class Main {
 2     
 3     public static void main(String[] args) {
 4         System.out.println(new Main().isRotation("cdab", "abcd"));
 5         System.out.println(new Main().isRotation("1ab2", "ab12"));
 6         System.out.println(new Main().isRotation("2ab1", "ab12"));
 7     }
 8     
 9     public boolean isRotation(String a, String b){
10         if(a == null || b == null || a.length() != b.length()) return false;
11         String b2 = b + b;
12         return b2.indexOf(a) != -1;
13     }
14     
15 }