字符串移位包含问题研究

痛定思痛。 2022-05-15 01:35 181阅读 0赞

问题：给定两个字符串s1和s2，要求判定s2是否能够通过s1做循环移位得到字符串包含，例如s1=AABCD，s2=CDAA，则返回true，如果s1=ABCD，s2=ACBD，则返回false。

解法1：对字符串做循环移位，然后判断移位后的字符串是否包含s2.这种方法需要穷举，效率较低。

public static boolean containStr1(String s1,String s2)
    	{
    		char[] str1=s1.toCharArray();
    		char[] str2=s2.toCharArray();
    		for(int i=0;i<str1.length;i++)
    		{
    			char temp=str1[0];
    			for(int j=0;j<str1.length-1;j++)
    			{
    				str1[j]=str1[j+1];
    			}
    			str1[str1.length-1]=temp;
    			if(charArrayContain(str1,str2))
    			{
    				return true;
    			}
    		}
    		return false;
    	}

上面用到了一个判断两个字符数组是否包含的函数，如下定义：

private static boolean charArrayContain(char[] s1,char[] s2)
    	{
    		if(s1==null||s2==null)
    			return false;
    		if(s1.length==0||s2.length==0)
    			return false;
    		if(s1.length>=s2.length)
    		{
    			int i=0,j=0;
    			while(i<s1.length&&s1[i]!=s2[j])
    			{
    				i++;
    			}
    			for(;i<s1.length&&j<s2.length;i++,j++)
    			{
    				if(s1[i]!=s2[j])
    					break;
    			}
    			if(j==s2.length)
    				return true;
    		}
    		return false;
    	}

除了上面的方法，还有更好的方法吗？下面介绍方法2

解法2：我们知道如果字符串s2可以通过s1移位后的字符串包含，那么字符串s2肯定在s1s1组合字符串中。下面我们使用JAVA自带的函数来写代码。

public static boolean containStr2(String s1,String s2)
    	{
    		s1=s1.concat(s1);
    		return s1.contains(s2);
    	}

是不是觉得很简洁，而且从运行结果来看，这个算法比解法1要快，需要注意的是这个方法是通过增加空间复杂度来较低时间的复杂度的。有人会想，Java自带的函数难道都很快能达到我们的要求吗？我也不确定，不过我们尝试自己写函数来实现解法2中的函数。如解法3所示：

解法3：该方法使用与解法2一样的思想，不同的是我们自己编写实现代码。

public static boolean containStr3(String s1,String s2)
    	{
    		char[] str1=new char[s1.length()+s1.length()];
    		for(int i=0;i<s1.length();i++)
    		{
    			str1[i]=s1.charAt(i);
    			str1[i+s1.length()]=s1.charAt(i);
    		}
    		char[] str2=s2.toCharArray();
    		return charArrayContain(str1,str2);
    	}

通过运行我们比较了一下两种速度，基本上还是差不多的呵呵。

那么除了上面的方法外，还有其它方法吗？还有更快的方法吗？接下来我们将另一种方法。

解法4：要想判断s1移位后的字符串是否包含s2，其实意思就是“如果我们把字符串看成是一个循环字符串，那么问s2字符串中的字符能否在s1这个循环字符串中顺序连续的出现，如果能，则说明包含，如果不能，则说明不包含！”。下面我们根据这个思路编写实现代码。如下所示：

public static boolean containStr4(String s1,String s2)
    	{
    		int i=0,j=0;
    		while(i<s1.length()&&s1.charAt(i)!=s2.charAt(j))
    			i++;
    		for(;i<s1.length()&&j<s2.length();)
    		{
    			if(s1.charAt(i)!=s2.charAt(j))
    				return false;
    			i=(i+1)%s1.length();
    			j++;
    		}
    		if(j==s2.length())
    			return true;
    		return false;
    	}

上面我们已经讲了好几种算法，下面给出这几种算法的运行结果：

true
    用时：199355纳秒
    true
    用时：49899纳秒
    true
    用时：43268纳秒
    true
    用时：35764纳秒

从运行结果就可以看出，解法4用时最少，是最快的算法，解法3和解法2基本差不多，解法1速度最慢。

欢迎讨论，转载请注明出处！