java找到最长的非重复子串-得到奇怪的结果

Question

我正在做一个经典的 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”

Answer 1

您有几个问题(请参阅我更正代码的评论):

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 .