查找不重复字符的最长子字符串-java

nuypyhwy  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(355)

我试图解决一个leetcode问题,但我的解决方案不是为某个测试用例返回正确的值。我想为这个解决方案实现两个指针技术(如果我使用了错误的技术,欢迎提供建议来解释正确的方法)。详情如下:
leetcode问题标题:
没有重复字符的最长子字符串。
问题:
给定一个字符串,求最长子字符串的长度,不要重复字符返回int)
我的解决方案:

public int lengthOfLongestSubstring(String s) {
        //place holder for me to create a "sub-string"
        String sub = "";

        //counter variable to count the characters in the substring
        int count = 0;
        int maxCount = 0;

        //my attempt at a TWO POINTER TECHNIQUE
        //pointers - to determine when the loop should break
        int head = 0;
        int tail = s.length();

        //this variable was intended to be used with the "indexOf" method, as the "start from" index...
        int index = 0;

        while(head < tail){
            //check if the next character in the string was already added to my substring.
            int val = sub.indexOf(s.charAt(head), index);

            //we proceed if it is -1 because this means the substring didnt previously contain that character
            if(val == -1){
                //added character to my substring
                sub+= s.charAt(head);
                count++;
                head++;
            } else {
                //reset data to default conditions, while continuing at the "head index" and check the rest of the substring
                count = 0;
                sub =  "";
            }
            //determine what the length of the longest substring.
            maxCount = count > maxCount ? count : maxCount;
        }
        return maxCount;
    }

我通过了测试用例:

> "" = expect 0
> " " = expect 1
> "abcabcbb" = expect 3
> "bbbbb" = expect 1
> "pwwkew" = expect 3
> "aab" = expect 2

我没有通过测试用例:

> "dvdgd" = expect 3, but got 2
> "dvjgdeds" = expect 5, but got 4
> "ddvbgdaeds" = expect 6, but got 4

可能的问题:
我相信发生这个问题是因为它用“v”传递索引,然后处理子字符串“dg”。因此,我试图更改解决方案,但修复该问题会导致我的所有其他案例返回错误,因此我认为应该放弃修复尝试。
我也尝试过:
我还尝试操作“indexof”方法来更改开始索引,只要在字符串中找到字符。然而,这产生了一个无限循环。
我已经试着解决这个问题好几个小时了,结果我累坏了。所以任何帮助都将不胜感激。如果可以,请详细解释,我对dsa和编程非常陌生,非常感谢。如果我需要更多的信息,请让我知道我会尽力回答。

1cklez4t

1cklez4t1#

好吧,给你:

public static int lengthOfLongestSubstring(String s) {
    //place holder for me to create a "sub-string"
    String sub = "";

    //counter variable to count the characters in the substring
    int count = 0;
    int maxCount = 0;

    //my attempt at a TWO POINTER TECHNIQUE
    //pointers - to determine when the loop should break
    int head = 0;
    int tail = s.length();

    //this variable shows where to start from 
    int index = 0;

    while(head < tail){
        //check if the next character in the string was already added to my substring.
        int val = sub.indexOf(s.charAt(head)); //search whole substing

        //we proceed if it is -1 because this means the substring didnt previously contain that character
        if(val == -1){
            //added character to my substring
            sub+= s.charAt(head);
            count++;
            head++;
            //determine what the length of the longest substring.
            maxCount = count > maxCount ? count : maxCount;
            System.out.println(sub); //let's see what we got so far
        } else {
            //reset data to default conditions, while continuing at the "head index" and check the rest of the substring
            count = 0;
            sub =  "";
            head=index+1; //begin from the next letter 
            index++; //move
        }

    }
    return maxCount;
}

相关问题