前往
大廳
主題

LeetCode - 93. Restore IP Addresses 解題心得

Not In My Back Yard | 2023-01-03 12:00:08 | 巴幣 2 | 人氣 240

題目連結:


題目意譯:
一個合法的 IP 地址由恰好四個整數組成,每個整數之間由單一一個點隔開。每個整數介於 0 到 255 之間(含端點兩數),並且不得含有前導零。

例如,"0.1.2.201" 和 "192.168.1.1" 都是合法的 IP 地址,但是 "0.011.255.245" 、 "192.168.1.312" 和 "192.168@1.1" 為不合法的 IP 地址。

給定一個只包含數字的字串 s,回傳藉由插入若干個點到 s 中所有可形成的合法 IP 地址。你可以按任意順序來排列這些 IP 地址。

限制:
1 ≦ s.length ≦ 20
s 只由數字組成。



範例測資:
範例 1:
輸入: s = "25525511135"
輸出: ["255.255.11.135","255.255.111.35"]

範例 2:
輸入: s = "0000"
輸出: ["0.0.0.0"]

範例 3:
輸入: s = "101023"
輸出: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]


解題思維:
就是單純地窮舉即可。

可以遞迴求每個整數部分各自是 s 的哪個字元到哪個字元,也可以直接窮舉 IP 的三個點要插入在哪些位置(s 最長 20 個字元,因此最多 C 19 取 3 = 969 種插入點的方式)。




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

創作回應

更多創作