牛骨文教育服务平台(让学习变的简单)
博文笔记

字符串移位包含问题

创建时间:2017-03-02 投稿人: 浏览次数:153

在《编程之美上》看到了字符串的移位包含问题:

给一个S1="AABCD",判断S2是否能通过S1移位得到,例如S2=“CDAA”,应该返回true。


解决一:蛮力法,就是双重循环,排列所有的可能性。

解决二:S1+S1=AABCDAABCD,那么S2就是S1+S1的子串,用CONTAINS就可以实现判断。


下面是亲测可用代码:

/** 
* * @author LilyLee
 * @date  2017年3月2日
 * @Version 
 *
 */
public class HelpTest { 
		public static final int MATCH = 1; 
		public static final int NOMATCH = 0; 
		private String source;
		public HelpTest(String source){
			this.source = source; 
			} 
		public int doMatch(String pattern) { 
			String str = this.source + this.source; 
			if(str.contains(pattern)){ 
				return MATCH; 
				}else{ return NOMATCH; 
				} 
			} 

	public static void main(String[] args){ 
				String s1="AABCD"; String s2="CDA";
				HelpTest ht = new HelpTest(s1); 
				if(ht.doMatch(s2)==HelpTest.MATCH){
					System.out.println("Contain!"); 
					}else{ System.out.println("Not Contain!"); } 
				} }
	  

然后书上最后还留了一个疑问,如果用S1+S1拼接,就是用空间换时间,能不能不浪费空间呢?

我查阅了一下资料,看到有C/C++的代码可以实现这个:

引用自:http://www.cnblogs.com/sooner/p/3270548.html

解法三:我们的想法是,在s1后面"虚拟"地接上一个s1,这个"虚拟的s1"并不占空间,但是仍然按照解法2的思路进行。那么,如何实现这个"虚拟的s1"呢?其实只要把s1的最后一个元素,再指回s1的第一个元素即可。这可以用取模运算实现。比如,元素s1[(d1+i) mod d1]其实就是那个“虚拟的s1”的第i个元素,这里 0<=i<=d1-1, d1是字符串s1的长度。

同理,指针也可以实现类似功能:


这个找一天有空了,我拿JAVA实现一下,我觉得这个想法还蛮有意思的~

声明:该文观点仅代表作者本人,牛骨文系教育信息发布平台,牛骨文仅提供信息存储空间服务。