LeetCode-93.IPアドレスの復元(関連話題:遡及)
数値のみを含む文字列を指定し、それを復元し、可能なすべてのIPアドレスフォーマットを返します.
例:
問題解決の構想:深度優先探索+遡及、注意しなければならないのは、毎回深度探索の時、各IPセグメントの長さ範囲を制限することができて、最も短いのは各未確定のIPセグメントが3文字の長さを占める時の残りの文字数(0より大きい必要がある)で、最も長いのは各未確定のIPセグメントが1文字の長さを占める時の残りの文字数(3より小さい必要がある)で、および文字'0'に対する処理
Javaコード:
例:
: "25525511135"
: ["255.255.11.135", "255.255.111.35"]
問題解決の構想:深度優先探索+遡及、注意しなければならないのは、毎回深度探索の時、各IPセグメントの長さ範囲を制限することができて、最も短いのは各未確定のIPセグメントが3文字の長さを占める時の残りの文字数(0より大きい必要がある)で、最も長いのは各未確定のIPセグメントが1文字の長さを占める時の残りの文字数(3より小さい必要がある)で、および文字'0'に対する処理
Javaコード:
class Solution {
public List restoreIpAddresses(String s) {
List res = new LinkedList<>();
if(4 > s.length() || 12 < s.length())
return res;
dfs(s, 0, 0, res);
return res;
}
private void dfs(String s, int index, int part, List res){
if(3 == part){
if("0".equals(s.substring(index, s.length())) ||
('0' != s.charAt(index) && Integer.parseInt(s.substring(index, s.length())) <= 255))
res.add(s);
return;
}
if('0' == s.charAt(index)){
dfs(s.substring(0, index+1) + "." + s.substring(index+1, s.length()), index+1+1, part+1, res);
} else {
for(int i = Math.max(s.length()-index-3*(4-part-1), 1); i <= Math.min(s.length()-index-1*(4-part-1), 3); i++){
if(Integer.parseInt(s.substring(index, index+i)) <= 255){
dfs(s.substring(0, index+i) + "." + s.substring(index+i, s.length()), index+i+1, part+1, res);
}
}
}
}
}