Skip to content

LeetCode: 3-Longest Substring Without Repeating Characters 解題紀錄

Last Updated on 2021-05-11 by Clay

題目

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

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

這是個非常單純的題目：輸入是唯一字串，我們要在其中找到字元不重複的子字串。

解題思路

我自己的第一感是建立個陣列/佇列/字串，在遍歷整個輸入字串，只要當前判斷的字元不存在於建立的陣列中，即將該字元加入此陣列；如果這個字元已經存在陣列中，則一直刪除陣列開頭的值，直到當前判斷的字元不存在於陣列中為止。

這個說來可能有些攏統，以下直接看看程式碼：

C++ 程式碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max_len = 0;
        deque<char> sub_str = {};
        
        for (int i=0; i<s.size(); i++) {
            while (find(sub_str.begin(), sub_str.end(), s[i]) != sub_str.end()) {
                sub_str.pop_front();
            }
            
            sub_str.push_back(s[i]);
            if (sub_str.size() > max_len) {
                max_len = sub_str.size();
            }
        }
        
        return max_len;
    }
};



Python 程式碼

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        sub_str = ''
        max_len = 0
        
        for w in s:
            while w in sub_str:
                sub_str = sub_str[1:]
            else:
                sub_str += w
                max_len = max(len(sub_str), max_len)
        
        return max_lenㄙㄟ



其中很有趣的是，Python 在切割時使用字串切割比陣列更快，我還是第一次知道這種事情。

References

Tags:

Leave a Reply