当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.003.Longest Substring Without Repeating Characters

LeetCode.003.Longest Substring Without Repeating Characters


题目描述

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3.

Note that the answer must be a substring, “pwke” is a subsequence and not a substring.


解题过程

最长连续不重复子串问题:从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度。

O(n^3)穷举法

穷举法非常耗时间,即便用集合来判断是否有重复也还需要O(n^3):

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

这是LeetCode Solution中给出的代码,allUnique()方法用哈希集合实现了O(n)判断是否有重复字符,才使复杂度降为O(n^3),否则这道题穷举法就是O(n^4)的复杂度。

我的使用Map的O(n)方法

我自己也想到了用Map的O(n)方法,当前子串放到Map中,每次遇到新字符判断是否重复,有重复则更新最大子串长度并从重复字符的下一个位置重新开始:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max=0;
        int len=0;
        String maxSub="";
        String sub="";
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i=0; i<s.length();){
            if(map.containsKey(s.charAt(i))){
                max = len>max ? len : max;
                maxSub = sub.length()>maxSub.length() ? sub : maxSub;
                len = 0;
                sub = "";
                i = map.get(s.charAt(i)) + 1;
                map.clear();
            }else{
                map.put(s.charAt(i), i);
                sub+=s.charAt(i);
                len++;
                i++;
            }
        }
        max = len>max ? len : max;
        maxSub = sub.length()>maxSub.length() ? sub : maxSub;
        System.out.println(maxSub);
        return max;
    }
}

调试几次提交后倒是通过了,但非常慢,只打败了1.8%的代码。而且虽然我写出来了,但思路不是很清晰,我自己也还有点不清楚这个方法到底对不对。

使用Set的O(n)方法

然后看Solution,这道题的Solution写的还是非常详细而全面的,给出的几种方法都很好。
有一种使用HashSet的O(n)方法,使用Set存储当前滑动窗口[i,j)中的元素,j不断右移,遇到和当前集合中重复的字符则停止,更新最大子串长度,也就是从i开始的最长不重复子串,然后i加1继续找从i+1开始的最长不重复子串。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

为什么每次更新滑动窗口左边界i后(即从集合中删除s[i]),右边界j不需要回退呢?因为从i到j-1组成的子串我们已经验证过没有重复元素(否则右边界也走不到j),所以右边界不用回退。
其实右边界j保持不动时,左边界i会一直增长到i’+1(i’是滑动窗口中和j重复的元素位置),因为对于以[i,i’]中的字符开头以j结尾的子串,肯定会有字符和和s[j]重复。基于这一点,我们可以对此方法再进行优化:每次出现重复字符后,i直接跳到i’+1的位置

使用Map的O(n)方法

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

此算法比上一个使用集合的算法的优化就在于:每次出现重复字符后,左边界直接跳到重复字符后一位置

使用数组下标做Map的O(n)方法

考虑到这里Map的key值只有字符,value值为整数,可以用int[]数组做Map

  • int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
  • int[128] for ASCII
  • int[256] for Extended ASCII

如下:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

由于index[]数组自动初始化为全0,所以没有重复字符时index[s.charAt(j)]为0也不会重置i值,就不需要额外判断是否有重复字符了,这个代码非常简洁,但很难理解。

关于为什么有重复字符时i的值要取map.get(s.charAt(j))i中的较大者,因为map.get(s.charAt(j))确实有可能比i小,这是由于每次i值跳到重复字符后一个位置后,我们并没有把Map中i位置之前的、不需要的元素删掉,这就造成了Map中可能有之前的不需要的元素和s[j]相同,此时不需要更新i值,比如abba,j=3时,遇到重复字符,s[j=3]==s[0]==’a’,map.get(s.charAt(j))是1,但此时i=2,下标2之前的任何下标值都已经废弃了,所以我们不用更新i。


GitHub代码


上一篇 LeetCode.206.Reverse Linked List

下一篇 LeetCode.002.Add Two Numbers

阅读
1,398
阅读预计6分钟
创建日期 2018-02-04
修改日期 2018-02-05
类别
百度推荐