leetcode 93. Restore IP Addresses DFS深度优先遍历

àì夳堔傛蜴生んèń 2022-06-08 02:39 147阅读 0赞

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地址，和[ leetcode 91. Decode Ways DP动态规划+DFS深度优先遍历][leetcode 91. Decode Ways DP_DFS]和[leetcode 639. Decode Ways II 动态规划DP][leetcode 639. Decode Ways II _DP]一模一样，是一个典型的DFS深度优先遍历问题。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution 
    {
        //深度优先遍历，DFS即可实现
        List<String> res=new ArrayList<String>();
        public List<String> restoreIpAddresses(String s) 
        {
            //特殊情况处理
            if(s==null || s.length()<=0 || s.length()<4 || s.length()>12)
                return res;
    
            String one="";
            byDFS(s,0,0,one);
            return res;
        }
    
        //index 记录开始的位置，k记录截取的数量，
        void byDFS(String s, int index,int k,String one) 
        {
            if(k==3)
            {
                String tmp = s.substring(index, s.length());
                if(check(tmp))
                    res.add(one+tmp);
                return ;
            }else
            {
                //每一次最长的截取长度是i，最短1位，最长3位
                for(int i=1;i<=3 && index+i < s.length() ;i++)
                {
                    String tmp = s.substring(index, index+i);
                    if(check(tmp))
                        byDFS(s, index+i, k+1, one+tmp+".");
                }
            }
        }
    
        public boolean check(String ip) 
        {
            //以0开始的字符串，只有0是合理的，其余的比如001等等都不是合理的
            if(ip.charAt(0)=='0')
            {
                if(ip.equals("0"))
                    return true;
                else
                    return false;
            }else
            {
                int ipNum=Integer.parseInt(ip);
                if(ipNum>0 && ipNum<=255)
                    return true;
                else
                    return false;
            }
        }
    }

下面是C++的做法，和上一道题一样，是很简单的DFS深度优先遍历的做法

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <sstream>
    #include <stack>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<string> res;
        vector<string> restoreIpAddresses(string s) 
        {
            if (s.length() <= 3)
                return res;
    
            string one = "";
            byDFS(s,0, 0, one);
            return res;
        }
    
        void byDFS(string s, int index, int k, string one)
        {
            if (k==3)
            {
                string tmp = s.substr(index);
                if (isVaild(tmp))
                    res.push_back(one + tmp);
                return;
            }
            else
            {
                for (int len = 1; len <= 3 && len+index<s.length(); len++)
                {
                    string tmp = s.substr(index, len);
                    if (isVaild(tmp))
                        byDFS(s,index+len,k+1,one+tmp+".");
                }
            }
        }
    
        bool isVaild(string s)
        {
            if (s[0] == '0')
            {
                if (s == "0")
                    return true;
                else
                    return false;
            }
            else
            {
                stringstream ss;
                ss << s;
                int num;
                ss >> num;
                if (num > 0 && num <= 255)
                    return true;
                else
                    return false;
            }
        }
    };

[leetcode 91. Decode Ways DP_DFS]: http://blog.csdn.net/jackzhang_123/article/details/77943849
[leetcode 639. Decode Ways II _DP]: http://blog.csdn.net/jackzhang_123/article/details/78860230