247. Strobogrammatic Number II
247. Strobogrammatic Number II
根據 Leetcode 的資料，這一題是 Google 常見的考題，這一題程式是很好寫，可是最困難的是這個問題的邏輯並不好想。
題目給的 n 的長度最大是到 14 ，看起來很小，不過這個數字真正代表的是最大的搜索區間是落在是 \([10^{13}, 10^{14}]\) 的，這個 n 是一個非常非常大的數字！如果已經做過題目 246. Strobogrammatic Number ， 的確可以想到用暴力解找到。
演算法的題目寫多了就會可以快速觀察到，如果今天我們要找的一個數字，是非常稀缺的話，暴力法一定不是一個好解法，像是 204. Count Primes 這題，質數是一個很難找的數字，尤其數字越大會越難找到，這一題最大的 n 可以是 14，不過在 14 位數的情況，大約是幾十兆的數字中，也才出現六萬兩千五百個數字而已，比例大概是 6.9444444e-10% 。
但是題目已經放在回溯法的區域了，所以可以快速的推論這題是要用回溯法來寫，但是這樣算是一個作弊，因為真實的面試情況，我們是不會知道題目應該要怎麼做的，所以我還是想要寫寫要怎麼樣想到用回溯法來寫？不過嚴格來說，這個題目只要窮舉，處理邏輯的方式和回朔法很像，但其實只是一個遞迴的問題，不過又不存在著重疊子問題，所以也不是動態規劃。
首先，先看這個題目的特性，是不是一個要我們窮舉所有可能的窮舉題？題目問的就是窮舉出所有的 Strobogrammatic Number，窮舉的空間非常大，就如同上方的分析，但是又因為是 Strobogrammatic Number 的特性，可以幫助快速的把窮舉的空間進行剪枝，大大的降低時間複雜度，其實我也是沒有信心在面試中是不是可以用窮舉的方法來進行，如同我其他篇文章的建議，禮貌性地問一下面試官，想法對不對，是不是在正確的方向上，好的公司與好的面試官應該要在這裡適時的給予指引。
到了這裡，大概可以寫出以下的結構，不過這就是這題困難的地方，其實有很多的細節還沒有處理到。
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
table = {
'1': '1',
'6': '9',
'8': '8',
'9': '6',
'0': '0'
}
ans = []
def backtrack(curr, n):
if n == 0:
ans.append(curr)
return
# TODO
backtrack(curr, n - ?)
backtrack('', n)
return ans第一個問題是，我們要怎麼樣不斷的窮舉使其符合 Strobogrammatic Number 的特性？應該有幾種情況
- 我從
0, 1, 8開始出發，當作最中間的數字，後面就很像處理回文問題一樣，往左右出發，產生出類似：609, 101, 818, 808...等數字，為什麼沒有考慮從6, 9出發呢？因為如果這兩個字在中間，會不符合 Strobogrammatic Number 的特性，所以最中間的數字，不能是6或9。 - 既然和回文問題很像，回顧一下回文問題的要注意的地方，那就是回文有兩種，一種是長度為奇數的情況，一種是長度為偶數的情況。其實上面的情況就是當長度為奇數的情況，如果長度為偶數的情況，基本上
- 最後一個要考量的點是，這個數字要是一個合法的數字，所以如果是
010這樣的數字，就是不合法的，如果是偶數長度的情況00也是不合法的，也就是說最左側與最右側的數字，不能是 0 。
綜合以上三點的分析，我們就可以進一步的去發展題目的演算法，首先我會想要先解決的是奇數與偶數的問題，和回文問題一樣，當最中間的值確定後，其實奇數回文的剩餘解法就會和偶數回文一樣，因此我會先處理這個問題。
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
table = {
'1': '1',
'6': '9',
'8': '8',
'9': '6',
'0': '0'
}
ans = []
def backtrack(curr, n):
if n == 0:
ans.append(curr)
return
# TODO
backtrack(curr, n - ?)
if n % 2 == 1:
for i in ['0', '1', '8']:
backtrack(i, n - 1)
else:
backtrack('', n)
return ans解決完上面的問題之後，剩下的基本上就和回朔法一樣，不斷地去探索答案，大致上的邏輯如下，回溯法內部的處理就是一種深度優先搜索的概念，處理的方式和回文很像，從中間向兩邊擴展，只是回文是前後要相等，這裡要處理的是前後要可以形成 Strobogrammatic Number 。
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
table = {
'1': '1',
'6': '9',
'8': '8',
'9': '6',
'0': '0'
}
ans = []
def backtrack(curr, n):
if n == 0:
ans.append(curr)
return
for key in table:
backtrack(key + curr + table[key], n - 2)
if n % 2 == 1:
for i in ['0', '1', '8']:
backtrack(i, n - 1)
else:
backtrack('', n)
return ans上面的解法還存在一個問題，這裡我們還漏了處理左側與最右側的數字，不能是 0 的情況，寫到這裡處理的方式就不難了，因為我們每次都新增左邊和右邊個一個數字，所以當 n == 2 時，我們就是要新增最右邊了兩個數字了，在這個時候如果 key 是 0 ，我們就要記得跳過不處理。
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
table = {
'1': '1',
'6': '9',
'8': '8',
'9': '6',
'0': '0'
}
ans = []
def backtrack(curr, n):
if n == 0:
ans.append(curr)
return
for key in table:
if n == 2 and key == '0':
continue
backtrack(key + curr + table[key], n - 2)
if n % 2 == 1:
for i in ['0', '1', '8']:
backtrack(i, n - 1)
else:
backtrack('', n)
return ans遞迴
有人分享了使用遞迴的解法，概念很類似，不過比較不好想到，放在這裡僅供參考。
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
odd = ['0', '1', '8']
even = ['11', '69', '88', '96', '00']
if n == 1:
return odd
elif n == 2:
return even[:-1]
else:
if n % 2:
prevs = self.findStrobogrammatic(n-1)
candidates = odd
else:
prevs = self.findStrobogrammatic(n-2)
candidates = even
mid = (n-1)//2
ans = []
for prev in prevs:
for candidate in candidates:
ans.append(prev[:mid] + candidate + prev[mid:])
return ans