【Lintcode】python – [680] Split String 個人解法筆記

➣ Reading Time: 5 minutes

題目出處

680 · Split String

難度

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)」,不然直接取座標會出錯

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 693

★留個言吧!內容有誤或想要補充也歡迎與我討論!