【题目】
如果一个字符串 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 }