前往
大廳
主題

LeetCode - 17. Letter Combinations of a Phone Number 解題心得

Not In My Back Yard | 2021-04-18 00:00:07 | 巴幣 0 | 人氣 339

題目連結:


題目意譯:
給定一字串包含著數字 2 ~ 9 之位數,回傳該數字能表示的所有可能之字母組合。可以任意順序回傳答案。

每個位數對應到的字母之表格給定如下。注意, 1 沒有對應到任何字母。

限制:
0 ≦ digits.length ≦ 4
digits[i] 為一位數其數字範圍為 ['2', '9']。



範例測資:
範例 1:
輸入: digits = "23"
輸出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

範例 2:
輸入: digits = ""
輸出: []

範例 3:
輸入: digits = "2"
輸出: ["a","b","c"]


解題思維:
典型的窮舉題型。

先將數字與字母的對應關係建立好。之後,可以使用深度優先搜尋(Depth First Search,DFS)一層一層地將每個數字對應的字母窮舉一遍然後遞迴到下一層,所有數字跑完之後就會得到一個可能字母組合。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作