【算法】字符串循环移位后是否可包含

2017-12-31 Algorithm 阅读量

问题

给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。
例如，s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。

解法一

最直接最笨的方法就对s1进行循环移动，再进行字符串包含的判断，从而遍历其所有的可能性。字符串循环移动，时间复杂度为O（n），字符串包含判断，采用普通的方法，时间复杂度为O（n*m），总体复杂度为O（n*n*m）。字符串包含判断，若采用KMP算法，时间复杂度为O（n），这样总体的复杂度为O（n*n）。若字符串的长度n较大，显然效率比较低。其中n为s1的长度，m为s2的长度。

解法二

对s1的循环移位操作，可以使用拼接s1+s1的方式得到。

以S1 = ABCD为例，先分析对S1进行循环移位之后的结果，如下所示：

ABCD—>BCDA—->CDAB—->DABC—->ABCD……

假设我们把前面的移走的数据进行保留，会发现有如下的规律：

ABCD—>ABCDA—->ABCDAB—->ABCDABC—->ABCDABCD……

因此，可以看出对s1做循环移位所得到的字符串都将是字符串s1s1的子字符串。如果s2可以由s1循环移位得到，那么s2一定在s1s1上，这样时间复杂度就降低了。

/**
 * 解法二，拼接字符串s1+s1
 * 如果s2可以由s1循环移位得到，那么s2一定在s1s1上
 */
public static boolean isContainsByConcat(String a, String b){
    if(a == null || b == null || a.isEmpty() || b.isEmpty()) return false;

	String newStr = a.concat(a);
	return newStr.contains(b);
}

解法三

使用指针循环。我们的想法是，在s1后面”虚拟”地接上一个s1，这个”虚拟的s1”并不占空间，但是仍然按照解法2的思路进行。那么，如何实现这个”虚拟的s1”呢？其实只要把s1的最后一个元素，再指回s1的第一个元素即可。这可以用取模.aspx)运算实现。比如，元素s1[(d1+i) mod d1]其实就是那个“虚拟的s1”的第i个元素，不会超出字符串s1的长度。

用一个指针标记遍历s1，最多两遍，与s2中的第一个字符比对，如果命中则进入s2，进行逐位匹配，匹配失败的话跳出s2继续查找s1。

/**
 * 解法三：指针循环查找
 */
public static boolean isContainsByPointer(String a, String b){
	if(a == null || b == null || a.isEmpty() || b.isEmpty()) return false;

	int p = 0;	//s1的指针

	int aLen = a.length();
	int bLen = b.length();
	for(int i = 0; i < aLen * 2; i++){
		char c1 = a.charAt(p % aLen);

		//匹配到第一个字符相同后，遍历s2字符串
		if(c1 == b.charAt(0)){
			for(int j = 0; j < bLen; j++){
				if(a.charAt((p + j) % aLen) != b.charAt(j)){
					break;	//本次不完全匹配，继续往后
				}
			}
			return true;
		}
		p++;
	}
	return false;
}

优点：

字符串长度较大时，效率依然较好；
不需要申请额外空间存储第二个s1

参考资料

字符串移位包含的问题