Leetcode 3. Longest Substring Without Repeating Characters -

Longest Substring Without Repeating Characters 題意 : 給一個字串s，找出不重複字符的最長子字串

Python

對字串s進行遍歷，創一個新的暫存字串temp，如果temp包含已出現的字元，去掉頭的字元，如果temp不含已出現的字元，把沒有出現過的字元加入temp暫存，最後用max比大小。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        temp =''
        maxlen=0
        
        for i in s:             #遍歷s
            while i in temp:    #如果包含已出現的數，去掉頭的數
                temp=temp[1:]
            else:
                temp+=i         #把沒有出現過的數加入temp暫存
                maxlen=max(len(temp),maxlen)
        return maxlen

此方法類似上面，只是換種寫法，只要當前判斷的字元不存在於建立的陣列中，將該字元加入此陣列；如果這個字元已經存在陣列中，則一直刪除陣列開頭的值，直到當前判斷的字元不存在於陣列中為止。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        l,r,max_len=0,0,0
        sub_str=set()
        while l <len(s) and r<len(s):
            if s[r] in sub_str:
                sub_str.remove(s[l])
                l+=1
            else:
                sub_str.add(s[r])
                r+=1
                max_len=max(r-1,max_len)
        return max_len

C++

i為string的index，j為遍歷遇到相同的字串時需要在之前出現各過的那個字串向右移一格，確保是回文且不重複的字串。

class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    const int n = s.length();
    int ans = 0;
    vector<int> Substring(128, -1);
    for (int i = 0, j = 0; j < n; ++j) {
      i = max(i,Substring[s[j]] + 1);  #遇到相同的字串時需要在之前出現各過的那個字串向右移一格
      ans = max(ans, j - i + 1);      #回文最大值
      Substring[s[j]] = j;            #更新的重複字串
    }
    return ans;
  }

Python

C++

相關