文章目錄

• 1 題目理解
• 2 回溯

1 題目理解

輸入：字符串s
輸出：可能的ip地址
規(guī)則：一個(gè)有效的ip地市是一連串?dāng)?shù)字，數(shù)字范圍在0到255，每個(gè)數(shù)字不能有前導(dǎo)0。例如"0.1.2.201" and "192.168.1.1"是有效ip地址。"0.011.255.245"不是有效地址。“192.168.1.312” and "192.168@1.1"也不是有效地址。

Example 1:

Input: s = “25525511135”
Output: [“255.255.11.135”,“255.255.111.35”]
Example 2:

Input: s = “0000”
Output: [“0.0.0.0”]
Example 3:

Input: s = “1111”
Output: [“1.1.1.1”]
Example 4:

Input: s = “010010”
Output: [“0.10.0.10”,“0.100.1.0”]

2 回溯

依次處理字符串的每一位。例如s=“25525511135”。
例如處理第0個(gè)2:2是一個(gè)單獨(dú)的值。
處理第1個(gè)5，可以是一個(gè)單獨(dú)的值5，也可以和前面的2合起來組成25。
處理第2個(gè)5，可以是一個(gè)單獨(dú)的值5，也可以和前面的25合起來組成255。
…
一般就是：
處理第n個(gè)字符，可以是一個(gè)單獨(dú)的值value1，也可以和前面部分的值preValue組合成一個(gè)新的數(shù)值value2。

大致思路是這樣的。在處理中會(huì)發(fā)現(xiàn)遇到0的情況。那就是preValue=0的時(shí)候，當(dāng)前字符就不能和preValue組成新的值了。沒有這個(gè)選項(xiàng)。

只有在生成的數(shù)字個(gè)數(shù)小于4個(gè)的時(shí)候，才可以形成單獨(dú)形成一個(gè)值value1。

class Solution {private char[] chars;private List<String> result;public List<String> restoreIpAddresses(String s) {if(s==null || s.length()<4) return new ArrayList<String>();this.chars = s.toCharArray();result = new ArrayList<String>();dfs(0,0,0,new ArrayList<Integer>());return result;}private void dfs(int index,int preValue,int numberCount,List<Integer> values){if(index>=chars.length){if(numberCount==4){StringBuilder strb = new StringBuilder();strb.append(values.get(0));for(int i=1;i<values.size();i++){strb.append(".").append(values.get(i));}result.add(strb.toString());}return;}if(numberCount>4) return;int value = chars[index]-'0';//單獨(dú)成為一個(gè)值if(numberCount<4) {values.add(value);dfs(index+1,value,numberCount+1,values);values.remove(values.size()-1);}//拼在前一個(gè)后面if(preValue>0){int newValue = preValue*10+value;if(newValue<=255){values.add(newValue);dfs(index+1,newValue,numberCount,values);values.remove(values.size()-1);}}} }

時(shí)間復(fù)雜度$O(4?2^n)$ ，n是字符串長(zhǎng)度。每一個(gè)字符都有2種選擇。對(duì)于每一個(gè)結(jié)果要拼裝回答案需要遍歷數(shù)組，數(shù)組長(zhǎng)度是4。

總結(jié)

以上是生活随笔為你收集整理的93. Restore IP Addresses的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。