Question

java 实现 一个字符串中不重复最长子串

求java 实现 一个字符串中不重复最长子串

Answer 1

/** 注意：如果一个函数有多个长度相等的不重复子串，本函数只能得到其中的第一个子串，
* 如果要输出所有子串，稍作修改即可
*/
public static String noDuplicate(String s) {
	/**
	 * 这个函数返回给定字符串中最长不重复子串 采用类似纸牌游戏拖板车的思维
	 */
	String result = ""; // 记录最终结果，即最长子串
	String sub = ""; // 记录当前纸牌串
	for (int i = 1; i < s.length(); i++) { // 一张张发牌
		String c = "" + s.charAt(i); // 当前新发下来的牌
		if (!sub.contains(c)) { // 如果当前纸牌串中不包含新发的牌
			sub += c; // 将新牌加入当前纸牌串
		} else { // 如果当前纸牌串中包含新发的牌
			if(result.length()<sub.length()){ //如果当前子串比最优记录长
				result = sub; // 更新最优记录
			}
			String[] temp = sub.split(c); //将子串按当前牌分割为两部分
			sub = temp[1]; // 取后一部分作新的当前纸牌串，丢弃重复牌及其前面部分
			sub+=c; // 将新牌加入当前纸牌串
		}
	}
	// 比较最后一个当前纸牌串与最优记录
	if(result.length()<sub.length()){ //如果当前子串比最优记录长
		result = sub; // 更新最优记录
	}
	return result; 
}

Answer 2

public static String noDuplicate(String str) {
    String sub = "";
    String result = "";
    for (int i = 0; i < str.length(); i++) {
        String c = "" + str.charAt(i);
        if (sub.contains(c)) {
            if (sub.length() > result.length()) {
                result = sub;
            }
            sub = "";
        }
        sub += c;
    }
    if (sub.length() > result.length()) {
        result = sub;
    }
    return result;
}

Answer 3

你需要的是在几个字符串中找出来一个不重复最长子串，还是写出一个不重复最长子串

追问

aabcdrwrqwrqerdeffhih 打印出abcdrw

追答

public static void longestNodupSubstring(String string)

{

int len = string.length();

if(len>0){

Map cursor = new HashMap();

cursor.put(string.charAt(0), 0);

int [] lengthAt = new int[string.length()];

lengthAt[0] =1;

int max =0;

for(int i = 1 ;i<len;i++){

char c = string.charAt(i);

if(cursor.containsKey(c)){

lengthAt[i] = Math.min(lengthAt[i-1]+1, i-cursor.get(c));

}else {

lengthAt[i] = lengthAt[i-1]+1;

}

max = Math.max(max, lengthAt[i]);

cursor.put(c, i);

}

for(int i=0;i<len;i++){

if(max == lengthAt[i]){

System.out.println(string.substring(i-max+1, i+1));

}

}

}

}

追问

亲，你能告诉你这个算法的原理是什么吗，max和min记录的是什么值，能详细解释一下嘛

追答

你在在主函数中调用

longestNodupSubstring("aabcdrwrqwrqerdeffhih"); 就可以了

追问

亲，我指的是不知道这个程序的思路，想让你讲解一下，怎么个流程

追答

亲，这个程序就是读取字符串的每一个字符。如果字符串重复了。max的值就减一。此时最大为max-1-min。执行这个过程完。比较值。就可以得出最大的值。

Answer 4

最长。。。。。。
字符串最长是多长。。。。

追问

aabcdrwrqwrqerdeffhih 打印出abcdrw

追答

public String longestStr(String str) {
StringBuilder sb = new StringBuilder();
String retStr = "";
for (char s : str.toCharArray()) {
if (!sb.toString().contains(String.valueOf(s))) {
sb.append(s);
if (retStr.length() < sb.length())
retStr = sb.toString();
} else {
sb.delete(0, sb.length());
}
}
return retStr;
}

是这个意思吧：

"asdfgasdfqwe`12123jkl我去阿斯顿我1234567890去维尔2体育即可"

返回

"1234567890去维尔"

求采纳!!!!!