数据结构与算法之无重复字符的最长子串

原创
05/17 22:31
阅读数 22

一、说明

    给定一个字符串,找出不含有重复字符的 最长子串 的长度。
    示例:
        给定 `"abcabcbb"` ,没有重复字符的最长子串是 `"abc"` ,那么长度就是3。
        给定 `"bbbbb"` ,最长的子串就是 `"b"` ,长度是1。
        给定 `"pwwkew"` ,最长子串是 `"wke"` ,长度是3。请注意答案必须是一个 子串 , `"pwke"` 是 _子序列_ 而不是子串。

二、解决方案参考

    1. Swift 语言

class LongestSubstringWithoutRepeatingCharacters {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var longest = 0, left = 0, set = Set<Character>()
        let sChars = Array(s)
        
        for (i, char) in sChars.enumerated() {
            if set.contains(char) {
                
                longest = max(longest, i - left)
                
                while sChars[left] != char {
                    set.remove(sChars[left])
                    left += 1
                }
                left += 1

            } else {
                set.insert(char)
            }
        }
        
        return max(longest, sChars.count - left)
    }
}

    2. JavaScript 语言

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  var hash = {};
  var start = 0;
  var ans = 0;

  for (var i = 0, len = s.length; i < len; i++) {
    var item = s[i];

    if (!hash[item])
      hash[item] = true;
    else {
      // item 已经在 substring 中存在了
      for (; ;) {
        if (s[start] === item) {
          start++;
          break;
        }

        hash[s[start]] = false;
        start++;
      }
    }

    ans = Math.max(ans, i - start + 1);
  }

  return ans;
};

    3. Python 语言

class Solution(object):
    def _lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = collections.defaultdict(int)
        l = ans = 0
        for i, c in enumerate(s):
            while l > 0 and d[c] > 0:
                d[s[i-l]] -= 1
                l -= 1
            d[c] += 1
            l += 1
            ans = max(ans, l)
        return ans
        
        
    def lengthOfLongestSubstring(self, s):
        d = {}
        start = 0
        ans = 0
        for i,c in enumerate(s):
            if c in d:
                start = max(start, d[c] + 1)
            d[c] = i
            ans = max(ans, i - start + 1)
        return ans

    4. Java 语言

// 方式一
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;
    }
}
// 方式二
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;
    }
}
// 方式三
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;
    }
}

    5. C++ 语言

#include <string.h>
#include <iostream>
#include <string>
#include <map>
using namespace std;
int lengthOfLongestSubstring1(string s) {
    map<char, int> m;
    int maxLen = 0;
    int lastRepeatPos = -1;
    for(int i=0; i<s.size(); i++){
        if (m.find(s[i])!=m.end() && lastRepeatPos < m[s[i]]) {
            lastRepeatPos = m[s[i]];
        }
        if ( i - lastRepeatPos > maxLen ){
            maxLen = i - lastRepeatPos;
        }
        m[s[i]] = i;
    }
    return maxLen;
}
//don't use <map>
int lengthOfLongestSubstring(string s) {
    const int MAX_CHARS = 256;
    int m[MAX_CHARS];
    memset(m, -1, sizeof(m));
    int maxLen = 0;
    int lastRepeatPos = -1;
    for(int i=0; i<s.size(); i++){
        if (m[s[i]]!=-1 && lastRepeatPos < m[s[i]]) {
            lastRepeatPos = m[s[i]];
        }
        if ( i - lastRepeatPos > maxLen ){
            maxLen = i - lastRepeatPos;
        }
        m[s[i]] = i;
    }
    return maxLen;
}
int main(int argc, char** argv)
{
    string s = "abcabcbb";
    cout << s << " : " << lengthOfLongestSubstring(s) << endl;
    s = "bbbbb";
    cout << s << " : " << lengthOfLongestSubstring(s) << endl;
    s = "bbabcdb";
    cout << s << " : " << lengthOfLongestSubstring(s) << endl;
    if (argc>1){
        s = argv[1];
        cout << s << " : " << lengthOfLongestSubstring(s) << endl;
    }
    return 0;
}

    6. C 语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int lengthOfLongestSubstring(char *s)
{
    int offset[128];
    int max_len = 0;
    int len = 0;
    int index = 0;

    memset(offset, 0xff, sizeof(offset));
    while (*s != '\0') {
        if (offset[*s] == -1) {
            len++;
        } else {
            if (index - offset[*s] > len) {
                len++;
            } else {
         len = index - offset[*s];
            }
        }
        if (len > max_len) {
            max_len = len;
        }
        offset[*s++] = index++;
    }

    return max_len;
}

int main(int argc, char **argv)
{
    if (argc != 2) {
        fprintf(stderr, "Usage: ./test string
");
        exit(-1);
    }

    printf("%d
", lengthOfLongestSubstring(argv[1]));
    return 0;
}

--------------------------------------

版权声明:本文为【PythonJsGo】博主的原创文章,转载请附上原文出处链接及本声明。

博主主页:https://my.oschina.net/u/3375733

本篇文章同步在个人公众号:

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部