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));           

}

或者，作为替代方案，您可以在内部循环的最后一次迭代中将当前 String 添加到 List 中：

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.

Answer 2

这里的问题是循环结构的最后一次迭代：

for (int i=0; i<tstring.length(); i++) {

  for (int j=i; j<tstring.length() - 1; j++) {

    ...

  }

}

如果我们采用你的 string wwhoamiUrektxineabcdefghijklmno，那么当i=30它将处理字符串的最后一个字符（“o”）时，但是 的长度tstring是 31 所以下一行（你的嵌套 for 循环）将不会运行为int j=30和tstring.length() - 1 = 30

相反，你应该开始下一个 for 循环int j = i + 1并让它运行到tstring.length()

关于何时向字符串添加字符以及何时决定需要将字符串添加到列表中，还存在一些逻辑问题。在这里试试这个...

for (int i = 0; i < tstring.length(); i++) {

  str += tstring.charAt(i);

  for (int j = i + 1; j<tstring.length(); j++) {

    compare= Character.toString(tstring.charAt(j));

    if (str.contains(compare)){

        break;

    } else {

        str += tstring.charAt(j);

    }

  }

  list.add(str);

  str = "";

}

最后，您不需要str位于循环外部。您可以在循环中实例化它（这将为您节省大约 2 行代码）。

Answer 3

for当您处于最后一个循环任务时，问题出在嵌套中。如果if不匹配，则不会将其添加str到列表中，并且不会重新发送str变量。为了解决这个问题，我稍微改变了你的源代码：

 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()-1; i++) { 

        for (int j=i+1; j<tstring.length(); j++) {

            str+= tstring.charAt(j-1);

            compare= Character.toString(tstring.charAt(j));

            if (str.contains(compare)){

                list.add(str);

                str="";

                break;

            }else{

                if (j==tstring.length()-1){

                    str+= tstring.charAt(j);

                    list.add(str);

                    str="";

                }

            } 

         }

       }

       //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));      

}

Answer 4

当 j 到达输入字符串的末尾而没有找到重复字符时，您不会将该子字符串添加到列表中，并且不会重置str。

尝试这样的事情：

    for (int i = 0; i < tstring.length(); i++) {

        String str = Character.toString(tstring.charAt(i));

        for (int j = i + 1; j < tstring.length(); j++) {

            char c = tstring.charAt(j);

            if (str.indexOf(c) >= 0) {

                break;

            }

            str += c;

        }

        list.add(str);

    }