UC知道字符串问题，高手请进
来源：百度知道 编辑：UC知道 时间：2024/06/01 23:39:21
（1）请写一个程序，产生由A，B，C，D，E这5个符号所构成、长度为n的所有满足下列条件的字符串：在字符串中对任何一个部分字符串而言，都不会有相邻的、完全相同的部分字符串。
（2）当给定的符号数不限定在5个符号，而可以是任意多个符号时，请编写出相对应的通用程序(如果字符串过长或过多，可只计算满足条件的字符串数)。
（3）试分析在5个字符情况下，要产生满足第（1）问条件的字符串，n有什么限制。
说明：比如出现字符串EBAA，这不符合要求，因为A与A相邻且相同；又比如出现字符串EABAB，这也不符合要求，因为AB与AB相邻且相同；诸如此类都是不符合要求的字符串。
能够打印所有符合条件的字符串。但是n过大的时候，会很慢，比如n=12，字符数为5个的时候，符合条件的字符串有11578800个。我不知道有没有什么快速的方法能够计算结果的数量。
对于第3问，貌似n没什么限制，因为在n=1000的时候，程序仍能找到合法的字符串。
我用的是回溯法。
public class Strs {
char[] chars;
final int len;
int count;
boolean print;
Strs(char[] chars, int len, boolean print) {
this.chars = chars.clone();
this.len = len;
this.print = print;
gen("");
System.out.println(count);
}
//检查字符串是否合法
boolean isValid(String s) {
final int len = s.length();
for(int i=1; i <= len/2; i++) {
String s1 = s.substring(len-i);
String s2 = s.substring(len-2*i, len-i);
if(s1.equals(s2)) return false;
}
return true;
}
//生成所有符合条件的字符串，由一个空串开始，逐步加长
void gen(String s) {
if(s.length() ==