/*
 * CC150 1.8
 * @author:Scarlett Chen
 * @date:12/22/2014 Mon 10:21 AM
 * 1.8 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").
 * 先利用String本来的method写一个简单的isSubstring
 *

 */
public class IsRotation {
	//看了别人的思路写的~
	//把rotation之后的s2再连上一个s2,如果s2是rotation的话，那么原字符串s1就必然是s2的substring
	//Time:o(n) Space O(1)
	public boolean isRotation(String s1,String s2) {
		if (s1==null && s2==null) return true;
		if (s1==null || s2==null) return false;
		int len1 = s1.length();
		int len2 = s2.length();
		if (len1 !=len2) return false;

		//核心代码
		return isSubstring(s1,s2+s2);
	}

	//一开始自己想的方法
	//Time: O(n^2),需要遍历每一个字符(o(n))。把s2里的每一个字符作为s1的开头，试着看能不能对得上(复制两个substring其实又是o(n))。
	//实际上in worst case, call了n次isSubstring.
	//不好。
	public boolean isRotation_Bad(String s1, String s2) {
		if (s1==null && s2==null) return true;
		if (s1==null || s2==null) return false;
		int len1 = s1.length();
		int len2 = s2.length();
		if (len1 !=len2) return false;

		//核心代码
		for (int i=0; i<len2; i++) {
			String latterHalf = s2.substring(i);
			if (isSubstring(latterHalf,s1))
			if ((latterHalf+s2.substring(0, i)).equals(s1)) return true;
		}
		return false;
	}

	// The assumed given method
	public static boolean isSubstring(String sub, String s) {
		return (s.indexOf(sub)!=-1)?true: false;
	}

}