字符串移位包含问题
在《编程之美上》看到了字符串的移位包含问题:
给一个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实现一下,我觉得这个想法还蛮有意思的~
声明:该文观点仅代表作者本人,牛骨文系教育信息发布平台,牛骨文仅提供信息存储空间服务。
- 上一篇: 字符串移位的解题技巧
- 下一篇: 字符串算法之字符串循环左移