程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode93:Restore IP Addresses

LeetCode93:Restore IP Addresses

編輯:C++入門知識

LeetCode93: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)


最開始看到這道題的時候也是毫無思路,囧啊。不過思考了一會兒,在紙上畫了一些圖示後發現可以按照這個思路求解。

這道題的主要思路是分治,將問題的規模不斷縮小。回溯中好多的題目都是使用這個思想來解題的。

IP地址被三個”.”分割成了4個部分,這裡我把每一個部分叫做一個段,依次為第0段,第1段,第2段,第3段。

那麼給定一個只包含數字的字符串,如果求出有效的ip地址呢?
以25525511135為例來分析。考慮第0段可能的取值,由於每一個段可以包含1位,2位或3位,那麼第0段可能的取值是:
2
25
255

第0段取值以後後面的字符串需要被分割成3段,那麼後面的字符能否被分割成3段呢?
第0段取上面的值後,剩余的部分依次為:
5525511135 ,字符串的長度為10,而3段最長也只能為9,所以第0段取2時沒有對應的有效ip地址。
525511135 ,這裡字符串的長度為9,即這個字符串還可能被分割成有效的3段。
25511135 ,這裡字符串的長度為8,即這個字符串還可能被分割成有效的3段。
然後再對525511135和25511135求分割成3段的方法。這裡問題規模就縮小了。需要被分割的段由4段變成了3了,字符串的長度也變短了。

遞歸退出的條件是遍歷到字符串尾端並且字符串被分割成了4段。

還需要注意的是:

如果一個段包含3個字符,那麼這三個字符不能大於”255”,這是ip地址的基本知識; 如果一個字符包括2個或3個字符,它的第一個字符不能為0。

runtime:4ms

class Solution {
public:
    vector restoreIpAddresses(string s) {
        vector result;
        string path;
        helper(s,0,0,path,result);
        return result;
    }

    void helper(string &s,int num,int pos,string &path,vector& result)
    {
        //遍歷完給定字符串,並且生成了個段時
        if(pos==s.size()&&num==4)
        {
            //這裡需要去除掉path最後的.
            result.push_back(path.substr(0,path.size()-1));
            return;
        }

        //如果該段包含的字符數大於規定的最大數目,那麼直接退出,可以把這個判斷放在下面的if中,
        //但是三個if都需要加,所以放在這兒更簡潔一些。
        if(s.size()-pos>3*(4-num))
            return;

        //該段只含有一個字符
        if(pos

另外幾道使用分治將問題規模縮小的使用回溯求解的題目:
LeetCode60:Permutation Sequence
LeetCode131:Palindrome Partitioning
LeetCode17:Letter Combinations of a Phone Number

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved