給一個字符串，如果遇到「#」，就等於按下Backspace鍵去修改字符串。

如果直接直譯規則書寫，寫起來就是那麼樸實無華且枯燥，這樣也能通過。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        newS = ""
        for char in S:
            if char == "#":
                if newS: newS = newS[:-1]
            else:
                newS += char
        newT = ""
        for char in T:
            if char == "#":
                if newT:
                    newT = newT[:-1]
            else:
                newT += char    
        return newS == newT

不過呢，題目希望我們能在 O(N)時間 並 O(1)空間 完成。

由於倒退符是往前刪除，因此由後往前對比就可以遇到#字再往前挪動。

指派一個 counter ，遇到 # 就 +1 ，非# 則 -1，使用 while 要跑到 counter 為 0 或是 跑到出界 為止。

這樣就無需使用到 O(N) 空間，用 O(1) 空間。同時也只需要跑一遍 N，花上 O(N) 時間。

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool: 
        # 回車函式
        def getPrev(text, pos):
            backspaceCounter = 1
            while backspaceCounter and pos >= 0:
                pos -= 1                    
                if text[pos] == "#": 
                    backspaceCounter += 1
                else:
                    backspaceCounter -= 1
            if pos >= 0: return pos           
            return -1

        SP, TP = getPrev(S, len(S)), getPrev(T, len(T))

        while SP > -1 and TP > -1:
            if S[SP] != T[TP]: break
            SP, TP = getPrev(S, SP), getPrev(T, TP)

        if TP == -1 and SP == -1: return True
        return False

要回傳 Linked List 中間的節點，如果長度是偶數，則中間偏右那一個。

有兩種解法：

第一種是跑完一遍得到長度，計算距離，再從頭跑到中間即可。前進距離是 length //2 。

第二種是用快慢指針，每回合快針走兩步，慢針走一步。當到了快針不能再走的回合，慢針會在中間的位置。

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        if not head: return head
        FP, SP = head, head
        while FP and FP.next:
            FP = FP.next.next
            SP = SP.next
        return SP

給一個數列，如果元素其值 +1 也在數列內的個數。如果有重複，則分開計算。

不多說甚麼，順一下解題邏輯。

如果要得知元素其值+1是否也存在於數列內，就得找完所有數列，並記錄元素是否有出現。

如果有重複出現，像是 1 1 2 2， 1 出現兩次且 2 在數列內，所以答案要加兩次。

於是記錄元素出現的時候，就要順便把其出現次數記錄下來。

最後跑完 memo 的鍵，鍵就是出現過的元素，若元素+1也在 memo 裡，答案就加上該元素的出現次數。

class Solution:
    def countElements(self, arr: List[int]) -> int:
        memo = dict()
        for num in arr:
            if num in memo: memo[num] += 1
            else: memo[num] = 1
        result = 0
        for key in memo:
            if key+1 in memo:
                result += memo[key]
        return result

Alice 跟 Bob 進行石頭遊戲，把石頭排成一排，一人一次拿 1 ~ 3 個，每個石頭都各有其分數，最後雙方誰持有的石頭分數總和高者勝。

這是 contest 的題目，在時限內沒有解出這一題，可惜。

雙方都會不會放水，採取最佳策略進行。這樣的情況下，如果是 Alice 贏就回傳 Alice，Bob 贏則 Bob，平手則 Tie。

這是一個博奕問題：有雙方，互相採取行動，兩者互相對抗。

當看到雙方都採取一樣的策略之時，雙方的判斷都是一樣的，因此用一個邏輯函數，就要能指出該下哪一步。

以拿走三顆石頭的時候來看，不論是此時是輪到 A 或者是 B ，兩者當前的最佳解都是一樣的。先後順序不影響決定最佳解，局面進行到哪裡才是。

因此，用一個 memo 記錄所有情形，其鍵會是拿走的數量或是剩餘的數量。這memo紀錄的分數對雙方都是一樣的。

接下來講一點博奕心理。

在選擇行動時，不一定會選擇當下分數最高的，如果最後要贏對手，採取行動原則是為了要讓自己領先對手加大差距，距離變化才是關鍵。

像是 -1 -2 -3 ，如果選擇分數最高的行動只拿 -1 ，對手會只拿 -2 ，最後你不得已只能拿 -3 而輸掉。

考量到對手的行動，你拿 -1 對手拿 -2 整體反倒被 對手拉近 1 的距離，若拿 -1 -2 對手會只能拿 -3，整體差距並沒有縮小，反到是更有利的選擇。

不過這沒提到後手再後手。你拿 -1 要思考對手的下一步， 而對手會思考對手的下一步再下一步，行動連鎖直到結束。連鎖到底，這種特性是遞迴。

整理一下觀察到的線索，推導出邏輯函數會是一個考慮拉大對手差距的遞迴函數。

那這個遞迴函數要回傳甚麼？

回到 -1 -2 -3 的例子，當你拿 -1，對手會採取最佳解，也就是剩下 -2 -3 的最佳拿法的分數。拿 -1 -2，也需要對手的最佳解。然後在三種選擇中，拿 -1 -2 是最佳解。

於是你可以找出當前狀況最佳解，回傳分數，遞迴往前傳，就能把最佳解一路往前推導。

最後來到起點，雙方一動也沒動的時候，此時由 Alice 先手，因此沒動過的最佳解，就是 Alice 的最佳下法的分數，如果為正的，意味著到最後 Alice 會贏那些分數。0則平手，負則輸掉。

class Solution:
    def stoneGameIII(self, stoneValue):     
        stones = len(stoneValue)
        pos = 0
        memo = {} # 使用座標當標籤

        def searchMaxRelativeScore(pos):   
            if pos in memo: return memo[pos]
            # 計算出當前剩餘個數            
            score = 0
            scores = []
            remains = min(stones - pos, 3)
            for i in range(remains):
                scores.append(sum(stoneValue[pos:pos+i+1]) - searchMaxRelativeScore(pos+i+1))
            if scores: score = max(scores)
            memo[pos] = score
            return score

        searchMaxRelativeScore(0)

        if memo[0] > 0: return "Alice"
        elif memo[0] == 0: return "Tie"
        else: return "Bob"

給一串 Doubly Linked List ，其中某節可能有 child ，要求你把這串 Doubly Linked List 平坦化，而 child 會插入在 該節 與 下一節 之間。

A – B – C – D – E        => A – B – F – G – C – D – E
      F  – G

寫一個遞迴函數，如果遇到 child ，你需要它的頭尾，針對這兩點修改就好。
(尾)G.next = B.next,  G.next.prev = G 、B.next = F(頭) , B.next.prev = B

於是遞迴函數的回傳值，就設定是 head 與 tail。

頭是搜尋的起點，有頭才能夠搜尋，而尾在尚未搜尋前是未知的，於是遞迴函數的回入值是頭節。

這樣在一路到底搜尋時，若是碰到 child，則把 child node 傳給遞迴函數，取得該子串的頭尾，然後插入當前的位置與下一位置的中間。

空間複雜度為 O(1)

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def nextNode(node):
            head = tail = node            
            while tail:
                if tail.child:
                    ch, ct = nextNode(tail.child)
                    if tail.next:
                        ct.next = tail.next
                        ct.next.prev = ct
                    tail.next = ch
                    tail.next.prev = tail
                    tail.child = None
                    tail = ct                   
                else:
                    if tail.next:
                        tail = tail.next
                    else:
                        break            
            return head, tail            
        return nextNode(head)[0]

另外一種則是先遍歷，記錄順序，最後再重組。

class Solution:    
    def flatten(self, head: 'Node') -> 'Node':
        nodes = []
        def nextNode(node):
            if node:
                nodes.append(node)
                nextNode(node.child)                
                nextNode(node.next)
        nextNode(head)
        p = None
        for each in nodes:
            each.child = None
            each.prev = p
            if p: p.next = each
            p = each
        return head

判別 Linked List 的值是否為回文。

凡是回文問題，就一定要知道長度，才能知道哪裡是分水嶺。

如果想用紀錄數值，最後再判別是否回文，由於該值可能為雙位數或是負數，如果想用 str 紀錄數值，就必須做特殊處理。

使用 list 紀錄，等過了分水嶺之後，就是該值與紀錄逐一對比，不符合就不是回文，找完就是回文。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        len_head = 1
        SP = FP = head
        while FP.next:
            len_head += 1
            FP = FP.next            
        #
        stack = []
        for _ in range(len_head//2):
            stack.append(SP.val)
            SP = SP.next
        if len_head%2==1: SP = SP.next
        while stack:
            if SP.val != stack.pop():
                return False
            SP = SP.next
                
        return True

簡化回文的判斷，使用 stack == stack[::-1]，這樣只需要比較一次，不用記錄長度，空間複雜度仍是 O(n)。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:     
        stack = []
        while head:
            stack.append(head.val)
            head = head.next      
        return stack == stack[::-1]

如果利用循環的概念，快指針走 長度-1 、 慢指針走 1 ，兩兩相相比，不相等就不是，直到快指針追到慢指針結束。

但是這樣會超時。

如果空間複雜度局限於 O(1)，就要使用 reverse 的概念，不論是把分水嶺前面的或後面的 reverse 都可以。反序完再兩兩比較。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        len_head = 1
        SP = FP = head
        while FP.next:
            len_head += 1
            FP = FP.next            
        #
        for _ in range(len_head//2):
            FP = SP
            SP = SP.next
            FP.next = head
            head = FP           
        if len_head%2==1: SP = SP.next
        while SP:
            if SP.val != head.val:
                return False
            SP = SP.next
            head = head.next
                
        return True

最近我的leetcode總是跑得比別人慢，即使是一樣的代碼，就是遜一節，不知道為什麼。

Remove all elements from a linked list of integers that have value val.

給一串 Linked List ，要刪除其中節點等於 val 的節點，並回傳頭節點。

這題不難，如果用快慢指針，就需要針對刪除頭部的狀況做判斷。

對我來說，要針對非題目所求的特別情況去做 if 判斷，這種寫法在我心中的「泛用性」就在及格邊緣搖搖欲墜。

這題已經離開了雙指針的子章節，應該是可以不用雙指針去解。

用了遞迴寫法，雖然版面簡潔許多，不過時間複雜度是紮實的 O(N)，每個節點都會修改。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        def nextNode(node):
            if node:
                node.next = nextNode(node.next)            
                if node.val == val: return node.next                    
            return node
        return nextNode(head)

上一題說到將 Linked List 反序，如果用反序的概念，也就是把目標值丟到最前方去。如此，最後只需要從頭跑 Linked List 直到不為目標值的時候，再把該節回傳。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:       
        if not head: return head
        FP =  SP = head
        FP = FP.next
        while FP:
            if FP.val == val:
                SP.next = SP.next.next
                FP.next = head
                head = FP
                FP = SP.next
            else:
                SP = SP.next
                FP = FP.next
        #
        while head and head.val == val:
            head = head.next
        return head

如果頭部移除的情形會很困擾，看了前段班的寫法，可以加入了暫時根節變成新頭根節，這樣可以把一切都當成子根節處理，最後回傳暫時根節的下一個(原頭根節)即可，就不需要針對頭根節移除自身做額外寫法。
# 前段班大神寫法

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:       
        head_holder = ListNode(0) # the value does not matter
        head_holder.next = head
        
        cur = head_holder
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next

        return head_holder.next

給兩串 ListNode，回傳 Intersection 的第一個點，如果沒有則回傳 None。

用 memo(hashset) 去紀錄 headA 所有走過的節。再換 headB 走，如果該節在 memo 裡，就是第一個交會點。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        memo = set()
        PointerA, PointerB = headA, headB
        while PointerA:
            memo.add(PointerA)
            PointerA = PointerA.next
        while PointerB:
            if PointerB in memo: return PointerB
            PointerB = PointerB.next           
        return None

有效歸有效，不過會消耗掉大量記憶體，在一個提示空間複雜度 O(1) 之下，這方法似乎不是最好的。

思考一下，如果要第一個交會，那麼兩者行走距離應該是最短的。但是這樣怎麼寫？

[左1右1]、[左1右2, 左2右1]、….。這樣的安排，太沒有效率了。

我一開始本來想用 traceback，這樣空間複雜度會超出 O(1)，就沒有把它寫完了。

看了一下前段班，共同點就是 headA跑完換到headB、headB跑完換到headA。

為什麼可以這樣做？

如果有交會，headA = A part + C part、headB = B part + C part。

兩者一起往下跑，跑完換別的跑，會變成 headA->headB = A part + C part + B part + C part、headB->headA = B part + C part + A part + C part。

A part + C part + B part =  B part + C part + A part，於是兩者將會在 C part 交會。

這是一個循環的技巧應用，如果有想到，就會快很多。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        PointerA, PointerB = headA, headB
        for _ in range(2):
            while PointerA and PointerB:
                PointerA = PointerA.next
                PointerB = PointerB.next
            if PointerA: PointerB = headA
            else: PointerA = headB
          
        while PointerA and PointerB:
            if PointerA == PointerB: return PointerA
            PointerA = PointerA.next
            PointerB = PointerB.next            
        return None

Given an array of strings, group anagrams together.

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output:
[
  [“ate”,”eat”,”tea”],
  [“nat”,”tan”],
  [“bat”]
]

把文字做分類，anagrams 意思是「 a word, phrase, or name formed by rearranging the letters of another, such as cinema , formed from iceman.」(google翻譯)

可以透過移動字母，去拼成另外一個字詞。

於是兩詞若是同一個字謎，兩詞中字母出現的種類是相同的，且字母的出現次數是相同。

要保留這兩個數值，就不能破壞詞的長度，於是去掉 set，接下來想到的是 sorted() ，同一字謎的詞都會跑出相同結果。

不過 sorted() 回傳的類型是 list，list是無法作為 set 或是 dict 的key。用 “”.join() 或是 tuple轉換後就可以當作key。

確定了鍵從何而來 ，該鍵的值要保存同一字謎的詞，所以是 dict()，dict[key] : list(str)。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        memo = dict()
        for word in strs:
            anagram = "".join(sorted(word))
            if anagram not in memo: memo[anagram] = [word]
            else: memo[anagram].append(word)
        return memo.values()

這種寫法跟前段班有明顯的差距，前段班不外乎使用 defaultdict()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        import collections
        memo = collections.defaultdict(list)
        for word in strs:
            memo[tuple(sorted(word))].append(word)
        return memo.values()

就效率上，使用模組是有幫助的，不過 Leetcode 沒有寫到是否可以使用，或者是能夠載入甚麼模組，對我來說，能夠不用就不用到。如果一定要用的部分，像是取隨機值，才會使用。

解過多次題目之後發現，如果是可用的模組，不使用import也可以直接使用。

來到了 Linked List 章節，很快就遇到這個問題，問你ListNode是否有裡面有循環。

此題位於子章節 Two Pointer Technique，所以我不用直覺想到的 memo 紀錄步驟的遞迴解法。

示範提到，使用兩個 Pointer，一個快一個慢，快的一次走兩步，慢的走一步。

兩個 Pointer 的起點都是 head，如果有循環，Fast Pointer 遲早會追上 Slow Pointer

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head
        fastPointer, slowPointer = head, head
        while 1:
            # FastPointer go 2 steps forward
            for _ in range(2):
                if fastPointer.next:
                    fastPointer = fastPointer.next
                    if fastPointer == slowPointer: 
                        return True                            
                else:
                    return False
            # SlowPointer go 1 steps forward
            for _ in range(1):
                slowPointer = slowPointer.next

這種寫法可以減少記憶體使用，空間複雜度為 O(1)。

另外一種用 memo 紀錄步驟的方法。

紀錄步驟是需要用到不會重複的值，如果只是 val，除非保證不會有相同 val，不然可能會出錯。

最保險起見的方法，是使用記憶體位置，作為是否曾經走過的依據。

幸好物件可以直接加入set，而物件在set中做為比較的數值是記憶體位置。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head
        memo = set()
        while head.next:
            if head in memo: return True
            memo.add(head)
            head = head.next
        return False 

我在想，如果要得加入一個有用的變數在裡面，到底要怎麼加？這才是勾起我的興致的發想。 想出來了，硬是要在裡面加入的 steps 紀錄步數。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head
        fastPointer, slowPointer = head, head
        steps = 0
        while fastPointer.next:
            fastPointer, steps = fastPointer.next, steps+1
            if fastPointer == slowPointer: return True                                           
            if steps%2==1: slowPointer = slowPointer.next                
        return False

接著看到 II，這次要回傳循環起點，如果用 memo 紀錄，這個問題只是將回傳False改成當前的節點。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return head
        memo = set()
        while head.next:
            if head in memo: return head
            else: memo.add(head)
            head = head.next            
        return None

如果用快慢指針來解要怎麼辦？在兩者相遇之後，把慢指針移回原點，快慢指針每次都指往前一步，就會在循環起點相遇。

解釋：快2步，慢1步，當慢指針到了循環起點時，快指針在循環中也走了循環起點距離。而兩者的所剩距離是 循環長度 – 循環起點距離。
因此，慢指針往前「循環長度 – 循環起點距離」，兩者就會在循環內的 (循環長度 – 循環起點距離)位置上相遇。
此時把慢指針挪回起點，慢快指針同時走一步，前進 循環起點距離 步時，慢指針會來到 循環起點， 快指針會來到 循環長度 的位置，也是循環起點，兩者在此相遇。

手稿示意圖

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return head
        FastPointer, SlowPointer = head, head
        while 1:
            # SlwoPointer go 1 step forward
            SlowPointer = SlowPointer.next            
            # FastPointer go 2 steps forward
            if FastPointer.next and FastPointer.next.next:
                FastPointer = FastPointer.next.next
                if FastPointer == SlowPointer: break
            else:
                return None
        # FP SP meet in cycle(CycleLength - pos)
        SlowPointer = head
        while 1:
            if FastPointer == SlowPointer: return FastPointer
            SlowPointer = SlowPointer.next
            FastPointer = FastPointer.next

給一串文字串列，問說哪些兩個組合可以變成 Palindrome 回文。

這兩兩組合會有前後順序的差異，如果用最直觀的暴力破解法，跑遍每個組合，時間複雜度會是 O(n*(n-1))，O(n**2)。

列在 trie 的範圍內，這提示我們要使用 trie 去建立搜尋樹。要如何建立能找出回文的 trie ？

想一下回文的特性，如果是回文，頭跟尾會是相等的，頭跟尾往中間移動的字也會兩兩相等。

abcd|dcba, s|lls, lls|sssll => abcd|abcd., s|s.ll, lls|lls.ss

如果用顛倒的字詞建立 trie ，在搜尋過程中就可以前尾兩兩對消，如果過程找到字詞，只要確保「 . 」之後找到底也是回文的就可以。

aa|a => a.a|a.

萬一輸入的字詞找完之前，就先找到比較短的顛倒字詞，也代表後面不會再有字可以添加，先後對消後，只需要針對搜尋詞還沒找部分做回文判斷即可。
class Solution:

    def palindromePairs(self, words):
        result = []
        if words:
            trie = {} #反向     
            # create Trie
            n = len(words)
            for i in range(n):
                cur = trie
                for char in words[i][::-1]:
                    if char not in cur:
                        cur[char] = {}
                    cur = cur[char]
                cur['end'] = i
            # 檢查對稱                
            def isSymmetry(word):                
                n = len(word)
                for i in range(n//2):
                    if word[i] != word[n-1-i]: return False
                return True       
            #
            def search1(idx, temp, cur):
                """搜尋當前字詞"""
                if temp:
                    # 如果過程中找到字詞，檢查當前的剩餘部分是否回文
                    if 'end' in cur and isSymmetry(temp) and idx != cur['end']:                        
                        result.append([idx, cur['end']])
                    if temp[0] in cur:
                        search1(idx, temp[1:], cur[temp[0]])
                else:
                    search2(idx, "", cur)            

            def search2(idx, temp, cur):
                """搜尋剩餘部分是否回文"""
                for key in cur:
                    if key == "end":
                        if isSymmetry(temp) and idx != cur['end']:
                            result.append([idx, cur['end']])                        
                    else:
                        search2(idx, temp+key, cur[key])   
            #
            for i in range(n):
                search1(i, words[i], trie)
            
        return result

在效率上還是太慢，我搜尋是用更廣的對稱，涵蓋更多的可能性。看了一下前段班的寫法，去找更好的思路。

如果在搜尋上，是把字文拆出「可能」組合成回文的部分搜尋，就能提升效率，但我那時有思考到這種方式，但沒有寫想到要怎麼寫，因為我trie總是用成一層層，所以被侷限了。

字詞可以整個直接當成字典的鍵使用，該鍵的值就是位置。

像是 abcd，如果要拆成回文形式，就得找出左右之分。

abcd 前組後：
abcd | “” => “”是回文 => dcba(前面部分反序) => [0,1] #前組後
abc | d => d是回文 => cba => not found
ab | cd => cd不是回文 => X
a | bcd => cbd不是回文 => X
“” | abcd => abcd不是回文 => X

換個字詞

s 前組後：
s | “” => “”是回文 => s => [3,3] => 不合規則
“” | s => s是回文 => “” => not found

lls 前組後：
lls | “” => “”是回文 => sll => not found
ll | s =>> s是回文 => ll => not found
l | ls => ls不是回文 => X
“” | lls => lls不是回文 => X

這樣的搜尋只有「前組後」，沒有考慮到「後組前」，要考慮 後組前 只要把字詞反序做搜尋。
lls 後組前：
sll(字詞反序) | “” => “”是回文 => lls => [2,2] => 不合規則
sl | l => l是回文 => ls => not found
s | ll => ll是回文 => s => [3,2] #後組前
“” | sll => sll不是回文 => X

這樣搜尋速度快不少，不過會有答案會重複，所以要想辦法去掉。

class Solution:
    def palindromePairs(self, words):
        table = dict(map(reversed, enumerate(words)))
        res = set()
        for i, word in enumerate(words):
            for k in range(len(word)+1):                
                a = word[:k]
                b = word[k:]

                if a == a[::-1] and table.get(b[::-1], i) not in [-1, i]:
                    res.add((table.get(b[::-1], -1), i))
                    
                if b == b[::-1] and table.get(a[::-1], i) not in [-1, i]:
                    res.add((i, table.get(a[::-1], -1)))
                    
        return list(res)