題目出處
難度
medium
個人範例程式碼
from typing import (
List,
)
class Solution:
"""
@param s: a string to be split
@return: all possible split string array
"""
def split_string(self, s: str) -> List[List[str]]:
# write your code here
if not s:
return [[]]
self.ans = []
self.dfs(s, 0, [])
return self.ans
def dfs(self, s, start, combinations):
print(combinations)
# end of recursion
if start > len(s):
return
if start == len(s):
self.ans.append(list(combinations))
return
# define and split
combinations.append(f"{s[start]}")
self.dfs(s, start+1, combinations)
combinations.pop() # backtracking
if start + 1 < len(s):
combinations.append(f"{s[start:start+2]}")
self.dfs(s, start+2, combinations)
combinations.pop() # backtracking
算法說明
簡單來說就是一個求,「拿一個字母」或「拿兩個字母」的 組合題目。
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
注意:如果沒有 s,要回傳的是 [[]],而不是 []
Boundary conditions
注意邊界條件的設定
會有兩種情況
- start 超過 len(s),錯誤情況,預期不會發生 (也有被下面判斷式限制住)
- start 剛好等於 len(s),剛好的情況,就是我們要的答案
另外,判斷此層的 dfs 時,也有分兩種狀況
- s[start]:判斷一個字母的情況
- s[start:start+2]:判斷兩個字母的情況的,記得要先判斷「if start+1 < len(s)」,不然直接取座標會出錯