LeetCode #3 最長且沒有重複的子字串 - Zyrastory-當程式碰上美食

內容目錄

文章觀看次數: 768

LeetCode題目翻譯

英文原文如下

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

中文翻譯

給予一個字串 s ，找到裡面最長且沒有重複字元的子字串的長度

範例及題目限制

s 由英文字母、數字、符號及空白組成

解題思路

題目很容易理解的吧，就是不要出現重複的字元 ( 包含英文字母、數字、符號及空白 )

那讓我們用最簡單的List為例，看看要如何判斷 ( 這裡以C#為例 )

C# 解決方案

方案1 – list

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        
        if(string.IsNullOrEmpty(s))
        {
            return 0;
        }
        
        List<char>list = new List<char>();
        int max = 0;
        
        for(int i = 0;i<s.Length;i++)
        {
            char tmp = s[i];
            
            if(!list.Contains(tmp)) //確認list中有無此字元
            {
                list.Add(tmp);
            }
            else
            {
                max = Math.Max(max,list.Count); //更新最大值
                int ii = list.IndexOf(tmp);
                
                list.RemoveRange(0,ii+1);
                
                list.Add(tmp);
            }
        }
        
        if(list.Count != 0)
        {
            max = Math.Max(max,list.Count);  
        }
        
        return max;

    }
}

概念很簡單，就是對整個字串進行遞迴，然後用 list 中的 contains 判斷此字元有無出現過

重點是在於上面更新完最大值之後的判斷

int ii = list.IndexOf(tmp);

list.RemoveRange(0,ii+1);

這兩句做了甚麼呢?

第一句用indexOf 取得重複字元出現的地方，第二句則是將list那個位置以前的字元都清除

額…舉個範例吧，像是現在要判斷的單字是 “ABCD1BEF”

在第6個字元的時候會撞到重複的字元 B ，而這時候的list應該為 [“A”,”B”,”C”,”D”,”1″] 共5個

這時候 list.indexOf(“B”) 會得到 1

而 list.RemoveRange 中的第一個參數是起始索引，第二個是要移除的數量

所以在 list.RemoveRange(0,2) 之後，這時候的list就會變為 [“C”,”D”,”1″] 剩3個

然後再將該字元加上，所以最終變成 ➡ [“C”,”D”,”1″,”B”] ，然後又進入下一個遞迴

方案2 – HashSet + two pointers

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        
        if(string.IsNullOrEmpty(s))
        {
            return 0;
        }

        HashSet<char> hSet = new HashSet<char>();
        int max = 0;
        int i = 0;
        int j = 0;
        
        while(i<s.Length)
        {
            if(!hSet.Contains(s[i]))
            {
                hSet.Add(s[i]);
                i++;
                
            }
            else
            {
                max = Math.Max(max,hSet.Count);
                hSet.Remove(s[j]);
                j++;
            }
        }
        max = Math.Max(max,hSet.Count);
        return max;
        
    }
}

Solution3 – Dictionary

能用HashSet 那肯定也能用字典來替代了，就不特別說明了

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        Dictionary<char,int> dict =   new Dictionary<char,int>();
        int max = 0;
        
        for (int i = 0;i < s.Length;i++)
        {
            char c = s[i];
            if (!dict.ContainsKey(c))
            {
                dict.Add(c, i);
                max = Math.Max(dict.Count, max);
            }
            else
            {
                i = dict[c] ;
                dict.Clear();
            }
        }
        return max;   
    }
}

Java解決方案

方案1

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.isEmpty())
        {
            return 0;
        }

        ArrayList<Character>list = new ArrayList<Character>();
        int max = 0;
        
        for(int i = 0;i<s.length();i++)
        {
            char tmp = s.charAt(i);
            
            if(!list.contains(tmp))
            {
                list.add(tmp);
            }
            else
            {
                max = Math.max(max,list.size()); //check the max number
                int ii = list.indexOf(tmp);
                
                //list.removeRange(0,ii+1);
                list.subList(0,ii+1).clear();
                
                list.add(tmp);
            }
        }
        
        if(list.size() != 0)
        {
            max = Math.max(max,list.size());  
        }
        
        return max;

    }
}

方案2

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.isEmpty())
        {
            return 0;
        }

        HashSet<Character> hSet = new HashSet<Character>();
        int max = 0;
        int i = 0;
        int j = 0;
        
        while(i<s.length())
        {
            if(!hSet.contains(s.charAt(i)))
            {
                hSet.add(s.charAt(i));
                i++;
                max = Math.max(max,hSet.size());
            }
            else
            {
                //max = Math.max(max,hSet.size());
                hSet.remove(s.charAt(j));
                j++;
            }
        }
        //max = Math.max(max,hSet.size());
        return max;
    }
}

Python3 解決方案

方案1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == '':
            return 0;
        
        list1 = [];
        m = 0;
        
        for i in range(0,len(s)):
            tmp = s[i]
            
            if(tmp not in list1):
                list1.append(tmp);
            else:
                m = max(m,len(list1));
                i = list1.index(tmp);
                
                list1 = list1[i+1:];
                list1.append(tmp);
        
        if(len(list1)>0):
            m = max(m,len(list1));
            
        return m;

⭐方案2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == '':
            return 0;
        
        l = set();
        m = 0;
        i = 0;
        j = 0;
        
        while(i<len(s)):
            if(s[i] not in l):
                l.add(s[i])
                i+=1
            else:
                m = max(m,len(l));
                l.remove(s[j])
                j+=1
                
        m = max(m,len(l));
        return m;

JavaScript 解決方案

方案1

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    
    var mySet = new Set();

    var max = 0;
    var i = 0;
    var j = 0;

    while(i<s.length)
    {
        if(!mySet.has(s[i]))
        {
            mySet.add(s[i]);
            i++;
        }
        else
        {
            max = Math.max(max,mySet.size);
            mySet.delete(s[j]);
            j++;
        }
    }
    max = Math.max(max,mySet.size);
    return max;
};

結論

這一題有一點神奇，僅有34%左右的答案成功率，代表多數人的第一次都是錯誤的

不過其實筆者認為主要考的就是對各類型別清楚與否

你們看了以上的答案就會想說，應該也覺得不難的吧哈哈

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡幫我分享或是收藏，我都會很感激的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Longest Substring Without Repeating Characters – LeetCode

隨機文章

LeetCode #263 Ugly Number 醜的號碼

2024-02-08

LeetCode #202 Happy Number 快樂號碼

2023-01-30

LeetCode #509 Fibonacci Number 費波納契數

2023-07-22

LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量

2024-04-10

LeetCode #383 Ransom Note 勒索信 – 解題思路分享

2023-04-07

LeetCode #7 Reverse Integer 解題思路及翻譯

2022-05-17

LeetCode題目翻譯

解題思路

C# 解決方案

Java解決方案

Python3 解決方案

JavaScript 解決方案

結論

相關文章

發佈留言取消回覆