字符串——循环移位包含问题

题目：

给定两个字符串s1,s2，要求判断s2能否被s1循环移位得到的字符串包含。

例如给定s1="AABCD"和s2="CDAA“，返回true ；给定s1="ABCD"和s2="ACBD"，返回false。

方法一：构建辅助字符串，利用了额外的空间

解析：

构建一个辅助字符串s = s1+s1;

例如 s=s1+s1="ABCD"+"ABCD";

可以看出由s1做循环移位所得到的字符串都将是s的子串。至此问题转化成s2是否在s上的strstr问题。

public boolean rotateContains(String s1,String s2)
{
	if(s1 == null||s2 == null||s1.length()  <  s2.length())
		return false;
	StringBuilder sb=new StringBuilder(s1);
			sb.append(s1);
	return sb.toString().contains(s2);
	}

方法二：增强版的strstr方法

循环匹配s1和s2的字符，当s1达到末尾时，返回s1首部，继续匹配。

代码如下：

public boolean rotateContains(String s1,String s2)
{
	if(s1 == null||s2 == null||s1.length()  <  s2.length())
		return false;
	for(int i=0;i<s1.length();i++)//以s1的每个字符都作为匹配首部进行循环匹配
	{
		int j=0;
		for(;j<s2.length();j++)
		{
			if(s2.charAt(j)!=s1.charAt((i+j)%s1.length()))
					break;
		}
		if(j == s2.length())
			return true;
	}
	return false;
	}

阅读更多