iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 4
0
Software Development

刷刷題 or Alan Becker's game 製作 is a question 系列 第 4

LeetCode #3 : 3. Longest Substring Without Repeating Characters

  • 分享至 

  • xImage
  •  

誤解題意的解法 又適用於 Description 的各Example
錯誤示範#1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
            max = 0
            #length = 1
            print(len(s))
            
            for i in range(len(s)):
                length = 1
                print("i"+s[i])
                for j in range(i+1,len(s)):
                    if s[i]==s[j]:
                        print("repeat"+str(j)+" "+s[j])
                        print("max:"+str(max))
                        if length>max:
                            max = length
                        break
                    else:
                        length = length+1
                        print("len"+str(length))
                        #if length>max:
                            #print(str(length))
                            #max = length
                            
            print("Ans:"+str(max))
            if len(s)==1:
                return 1
            elif (len(s)!=0) and (max==0):
                return len(s)
            return max

看了別人思路,懂了這題的 substring 的意思。
紀錄之前有出現的字母,後續如果有出現則ignore?

錯誤示範#2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = set()
        for i in range(len(s)):
            ans.add(s[i])
        print(len(ans))
        return len(ans)

正解

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = set()
        left,right = 0,0
        res = 0 
        #for i in range(len(s)):
        while left < len(s) and right < len(s):
            if s[left] in ans and s[right] in ans:
                ans.remove(s[left])
                #left = right
                left = left + 1
            else:
                ans.add(s[right])
                right = right + 1
                res = max(res,len(ans))
            #ans.add(s[])
        print(ans)
        return res
        
        

Reference: https://blog.csdn.net/fuxuemingzhu/article/details/82022530


正解思路 內化
sol : 雙指標 left,right
都往右移
left 往右移的時機點是 s[right] 和 s[left] 都在set 裡,也就是碰到重複的字母。
而 right 往右移時機點是 目前位置指向的字母不在 set 裡,同時 set add 不曾出現的字母,
並且 更新最長子字串的長度: 目前記錄 vs 歷史紀錄 取 max。
note : Python set 存 無序不重複元素


上一篇
硬要 list 但要怎麼轉呢? - Medium Level : 2. Add Two Numbers
下一篇
830. Positions of Large Groups
系列文
刷刷題 or Alan Becker's game 製作 is a question 30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言