93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:


Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

一刷

題解:

  1. 題目給定的restoreIpAddresses方法
  1. 這里我們首先確定要用到遞歸 + 回溯。 并且我們要了解,合理的ipv4地址是由4段組成窖剑,而且每一段的值都在 [0 烟央, 255] 之間

  2. 在這個(gè)方法里面,我們要做一些基本的邊界判斷,比如s 是否為null, s的length 是否在 4 和 12之間。

  3. 構(gòu)造好用來遞歸求解的方法restoreIp砍濒,確定好每個(gè)要用的參數(shù)。

  4. 返回結(jié)果

  1. restoreIp方法
  1. 這個(gè)方法是我們主要進(jìn)行處理和判斷的方法硫麻。我們也分為兩個(gè)部分

  2. 判斷并返回結(jié)果:

當(dāng)我們用來保存ip地址List ip長(zhǎng)度已經(jīng)等于4的時(shí)候

我們判斷記錄當(dāng)前position的int pos是否正好等于String s的長(zhǎng)度爸邢, 假如否,我們返回

否則拿愧,這時(shí)我們找到一個(gè)合理的解杠河。可以建立一個(gè)StringBuilder ipSb,重建出這個(gè)ip address感猛,將其加入結(jié)果集 res中七扰,返回

  1. 遞歸求解:

這里我們要從i = pos, 到i < s.length() && i < pos + 3來進(jìn)行遍歷陪白。 因?yàn)閕p每一部分最多只有3個(gè)digit颈走,所以我們有這個(gè)pos + 3的constraint

每次先求得當(dāng)前的ip segment = s.substring(i, pos + 1)

接下來進(jìn)行判斷, 調(diào)用isIpValid方法

假如當(dāng)前ip segment合理咱士, 我們將這段ip segment加入到list ip中

遞歸調(diào)用restoreIp(res, list, s, i + 1)進(jìn)行下一步求解

進(jìn)行回溯立由,去除掉之前加入的這段ip segment

否則我們?cè)黾觟,繼續(xù)嘗試下一個(gè)ip segment序厉, 直到i = pos + 3時(shí)跳出循環(huán)

  1. isIpValid方法

這個(gè)方法主要用來確定ip segment是否合理:

首先s為null或者""的時(shí)候返回false

當(dāng)s的首字符為'0'的時(shí)候锐膜,我們要判斷是否整個(gè)s為"0"。 假如是弛房,我們返回true道盏, 假如否,那么這次切割結(jié)果"0x"不合理文捶,我們返回false

求出ip segment的int值荷逞,然后返回這個(gè) ipInt是否 >= 0 并且 <= 255

粗略的時(shí)間和空間復(fù)雜度估計(jì)為O(2n),但因?yàn)橛泻芏嗟募糁Υ馀牛衧ubstring()种远,而且n的范圍是在4和12之間,所以詳細(xì)復(fù)雜度并不高顽耳,但也并不好算坠敷。

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length()<4 || s.length()>12) return res;
        restoreIp(res, new ArrayList<>(), s, 0);
        return res;
    }
    
    private void restoreIp(List<String> res, List<String> ip, String s, int pos){
        if(ip.size() == 4){
            if(pos!=s.length()) return;
            //changeListToString
            String ipString = changeListToString(ip);
            res.add(ipString);
        }
        
        for(int i=pos; i<s.length() && i<pos+3; i++){//maximum is 3 char
            String ipseg = s.substring(pos, i+1);
            if(isValid(ipseg)){
                ip.add(ipseg);
                restoreIp(res, ip, s, i+1);
                ip.remove(ip.size()-1);
            }
        }
    }
    
    private String changeListToString(List<String> ip){
        StringBuilder sb = new StringBuilder();
        for(String str : ip){
            sb.append(str).append(".");
        }
        sb.setLength(sb.length()-1);
        return sb.toString();
    }
    
    private boolean isValid(String s){
        if(s == null || s.length() == 0) return false;
        if(s.charAt(0) == '0') return s.equals("0");
        int num = Integer.parseInt(s);
        return (num>=0 && num<=255);
    }
}

二刷
題解:
對(duì)于一個(gè)str和起始位置,從起始位置分別截取一段長(zhǎng)度為1射富,2膝迎,3的字串,然后進(jìn)入新的一輪dfs.

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length()<4 || s.length()>12) return res;
        dfs(res, new ArrayList<>(), s, 0);
        return res;
    }
    
    private void dfs(List<String> res, List<String> ip, String s, int pos){
        if(ip.size() == 4){
            if(pos!=s.length()) return;
            //changeListToString
            String ipString = changeListToString(ip);
            res.add(ipString);
        }
        
        for(int i=pos; i<s.length() && i<pos+3; i++){
            String ipseg = s.substring(pos, i+1);
            if(isValid(ipseg)){
                ip.add(ipseg);
                dfs(res, ip, s, i+1);
                ip.remove(ip.size()-1);
            }
        }
    }
    
    private String changeListToString(List<String> ip){
        StringBuilder sb = new StringBuilder();
        sb.append(ip.get(0));
        for(int i=1; i<ip.size(); i++){
            sb.append(".");
            sb.append(ip.get(i));
        }
        return sb.toString();
    }
    
    private boolean isValid(String str){
        if(str == null || str.length() == 0) return false;
        if(str.charAt(0) == '0') return str.equals("0");
        int num = Integer.parseInt(str);
        return (num>=0 && num<=255);
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末辉浦,一起剝皮案震驚了整個(gè)濱河市弄抬,隨后出現(xiàn)的幾起案子茎辐,更是在濱河造成了極大的恐慌宪郊,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,826評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拖陆,死亡現(xiàn)場(chǎng)離奇詭異弛槐,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)依啰,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,968評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門乎串,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人速警,你說我怎么就攤上這事叹誉⊙炝剑” “怎么了?”我有些...
    開封第一講書人閱讀 164,234評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵长豁,是天一觀的道長(zhǎng)钧唐。 經(jīng)常有香客問我,道長(zhǎng)匠襟,這世上最難降的妖魔是什么钝侠? 我笑而不...
    開封第一講書人閱讀 58,562評(píng)論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮酸舍,結(jié)果婚禮上帅韧,老公的妹妹穿的比我還像新娘。我一直安慰自己啃勉,他們只是感情好忽舟,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,611評(píng)論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著淮阐,像睡著了一般萧诫。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上枝嘶,一...
    開封第一講書人閱讀 51,482評(píng)論 1 302
  • 那天帘饶,我揣著相機(jī)與錄音,去河邊找鬼群扶。 笑死及刻,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的竞阐。 我是一名探鬼主播缴饭,決...
    沈念sama閱讀 40,271評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼骆莹,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼颗搂!你這毒婦竟也來了幕垦?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,166評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤先改,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后仇奶,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,608評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,814評(píng)論 3 336
  • 正文 我和宋清朗相戀三年别惦,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了夫椭。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片步咪。...
    茶點(diǎn)故事閱讀 39,926評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡益楼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出感凤,到底是詐尸還是另有隱情,我是刑警寧澤陪竿,帶...
    沈念sama閱讀 35,644評(píng)論 5 346
  • 正文 年R本政府宣布,位于F島的核電站闰挡,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏长酗。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,249評(píng)論 3 329
  • 文/蒙蒙 一夺脾、第九天 我趴在偏房一處隱蔽的房頂上張望茉继。 院中可真熱鬧咧叭,春花似錦烁竭、人聲如沸菲茬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,866評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽腥刹。三九已至马胧,卻和暖如春衔峰,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,991評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工威彰, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人穴肘。 一個(gè)月前我還...
    沈念sama閱讀 48,063評(píng)論 3 370
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像评抚,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子慨代,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,871評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容