iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
自我挑戰組

每日LeetCode解題紀錄系列 第 18

LeetCode解題 Day18

282. Expression Add Operators

https://leetcode.com/problems/expression-add-operators/


題目解釋

題目會給一組全部都是數字的字串,還有一個數字target ,請用+、-、*組出能得到target的算式,並回傳所有可能結果

example

https://i.imgur.com/hUbrypQ.png


解法

今天的題目一看就知道要用backtracking,但我還是寫不出來就是了/images/emoticon/emoticon20.gif

所以今天我就來分享看懂解答的過程,所以先上程式碼吧

程式碼

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        
        def backtracking(index, prev, curr, n, path):

            if index == len(num):
                
                if target == n and curr == 0:
                    ans.append(''.join(path[1:]))
                return 
            
            curr = curr * 10 + int(num[index])
            
            if curr > 0: #一大坨東西
                backtracking(index+1, prev, curr, n, path)
            
            # 加
            backtracking(index+1, curr, 0, n + curr, path + ['+', str(curr)])

            if path:
                #減
                backtracking(index+1, -curr, 0, n - curr, path + ['-', str(curr)])
                
                #乘
                backtracking(index+1, prev * curr, 0, n - prev + prev * curr, path + ['*', str(curr)])

            
        
        ans = []
        backtracking(0, 0, 0, 0, [])
        
        return ans

那我們就重頭開始吧!

  1. 首先,我們先定義一個backtracking 函數,裡面5個參數代表目前字串位置、前一個數字、現在數字、算式累積結果、目前的算式
def backtracking(index, prev, curr, n, path)
  1. backtracking都會有個中斷條件,要嘛發現不能做了,要嘛做完大功告成

而這題的結束且有結果的條件有3個:

  • 我們的指標已經到尾端了
  • 我們手上的東西都處理完了
  • 算式的結果符合題目要求
if index == len(num):

    if target == n and curr == 0:
        ans.append(''.join(path[1:]))
    return 
  1. 接著,我們先來看現在數字的計算
curr = curr * 10 + int(num[index])

算式裡的curr * 10是因為字串裡的數字不只能當成個位數,也能組成二位數、三位數...

如果curr = 0的話,就是把數字當個位數處理

  1. 這部分就是專門處理組合多位數的,要求大於0的原因我覺得很難講,只能請大家印出來自行體會
if curr > 0: #一大坨東西
    backtracking(index+1, prev, curr, n, path)
  1. 接著,我們看相加的部分
backtracking(index+1, curr, 0, n + curr, path + ['+', str(curr)])

prev的欄位放curr是因為我們目前的數字對下個backtracking的數字來說是先前數字;curr的欄位放0則可以當成是一個新開始的算式;累積的結果加上去就好

  1. 相減的部分也差不多,不過在那之前有個if path的判斷式,可以想成是要有東西可以減才成執行
backtracking(index+1, -curr, 0, n - curr, path + ['-', str(curr)])
  1. 乘法看起來比較不一樣,在累積結果的部分出現減法是因為乘號的優先度較高,感覺如下面這張圖
    https://i.imgur.com/MpTs9LJ.png
    backtracking(index+1, prev * curr, 0, n - prev + prev * curr, path + ['*', str(curr)])

  2. 連我自己都看不懂我在打什麼了,建議還是自己動手拿紙筆模擬一遍好了


閒聊

今天的題目是這個月第一次用到回朔法,結果就直接來hard題目了

如果有人和我一樣想不出來只能看解答的

看完後可以試解這題來看看自己是否已理解解答


上一篇
LeetCode解題 Day17
下一篇
LeetCode解題 Day19
系列文
每日LeetCode解題紀錄30

尚未有邦友留言

立即登入留言