我正在做一个经典的 leet 代码问题:找到字符串中最长的非重复子字符串。虽然堆栈溢出有很多类似的问题。我挠了挠头好几个小时,不知道为什么我的代码会产生这种奇怪的结果。希望有人能告诉我为什么我的
我是用Java做的
public static void main( String[] args )
{
String s= "wwhoamiUrektxineabcdefghijklmno";
longestNonRepeatStr(s);
}
public static void longestNonRepeatStr(String tstring) {
String str="";
String compare="";
List<String> list= new ArrayList<String>();
int biggest =0;
//find the nonrepeating string in each loop and add to list str
for (int i=0; i<tstring.length(); i++) {
for (int j=i; j<tstring.length()-1; j++) {
str+= tstring.charAt(j);
compare= Character.toString(tstring.charAt(j+1));
if (str.contains(compare)){
list.add(str);
str="";
break;
}
}
}
//find the longest nonrepeating string in the list
for (int i=0; i<list.size(); i++) {
if (list.get(biggest).length()< list.get(i).length()) {
biggest=i;
}
}
System.out.println(list);
System.out.println(list.get(biggest));
}
对于输入字符串
"wwhoamiUrektxineabcdefghijklmno"
输出是
"abcdefghijklmnb"
但是错了,最后一个字母应该是“o”
最佳答案
您有几个问题(请参阅我更正代码的评论):
public static void longestNonRepeatStr(String tstring) {
String str="";
String compare="";
List<String> list= new ArrayList<String>();
int biggest =0;
for (int i=0; i<tstring.length(); i++) {
str = ""; // you must clear the current String before each iteration of the inner loop
for (int j=i; j<tstring.length(); j++) { // here you were skipping the last character
str+= tstring.charAt(j);
// I improved the following condition
if (j+1 < tstring.length() && str.contains(Character.toString(tstring.charAt(j+1)))){
list.add(str);
str="";
break;
}
}
if (str.length() > 0) { // if you finish the inner loop without breaking, you should
// add the current String to the List
list.add(str);
}
}
for (int i=0; i<list.size(); i++) {
if (list.get(biggest).length()< list.get(i).length()) {
biggest=i;
}
}
System.out.println(list);
System.out.println(list.get(biggest));
}
或者,作为替代方案,您可以在内循环的最后一次迭代中将当前字符串添加到列表中:
public static void longestNonRepeatStr(String tstring) {
String str="";
String compare="";
List<String> list= new ArrayList<String>();
int biggest =0;
for (int i=0; i<tstring.length(); i++) {
str = "";
for (int j=i; j<tstring.length(); j++) {
str+= tstring.charAt(j);
if (j+1 >= tstring.length() || str.contains(Character.toString(tstring.charAt(j+1)))){
list.add(str);
str="";
break;
}
}
}
for (int i=0; i<list.size(); i++) {
if (list.get(biggest).length()< list.get(i).length()) {
biggest=i;
}
}
System.out.println(list);
System.out.println(list.get(biggest));
}
进一步解释如何获得输出“abcdefghijklmnb”:
当 i==16
,你的内部循环构建了 String
“abcdefghijklmn”。然后它会跳过“o”,因为您过早地结束了该循环(由于 j<tstring.length()-1
)。这String
尚未添加到 List
,因为您没有检测到重复字符。现在当i==17
,您将“b”附加到 str
并获得“abcdefghijklmnb”。现在你检查下一个字符“c”是否已经出现在str
中。 ,即 true
,因此您将“abcdefghijklmnb”添加到您的 List
.
关于java找到最长的非重复子串-得到奇怪的结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58265179/