Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g., "waterbottle" is a rotation of "erbottlewat").
Hint
- If a string is a rotation of another, then it's a rotation at a particular point. For example, a rotation of waterbottle at character 3 means cutting waterbottle at character 3 and putting the right half (erbottle) before the left half (wat).
- We are essentially asking if there's a way of splitting the first string into two parts, x and y, such that the first string is xy and the second string is yx. For example, x = wat and y = erbottle. The first string is xy = waterbottle. The second string is yx = erbottlewat.
- Think about the earlier hint. Then think about what happens when you concatenate erbottlewat to itself. You get erbottlewaterbottlewat.
Solution
本題給定兩個(gè)字符串，讓我們判斷其中一個(gè)字符串是否為另一個(gè)的旋轉(zhuǎn)字符串，此外還給了一個(gè)isSubstring函數(shù)來調(diào)用，不過規(guī)定只能調(diào)用一次宰闰。這里可以發(fā)現(xiàn)一個(gè)規(guī)律，若將一個(gè)字符串重復(fù)拼接，假如另一個(gè)字符串是拼接后字符串的子串贼邓，則它們就互為旋轉(zhuǎn)字符串。
令 x = wat, y = erbottle
若有 s1 = xy, s2 = yx闷尿，顯然它們互為旋轉(zhuǎn)字符串
重復(fù)拼接 s1s1 = xyxy, 則可以看到 s2 為 s1s1 的子串
public boolean isStringRotation(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
return isSubstring(s1 + s1, s2);
}
