93.Restore IP Addresses

tags: Medium,String,Backtracking

93. Restore IP Addresses

題目描述

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

• For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

範例

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 = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

• 1 <= s.length <= 20
• s consists of digits only.

解答

C++

作法

1. backtracking走一遍

class Solution {
public:
    vector<string> ans;
    void BT(const string &s, string address = "", string cur = "", int i = 0) {
        if (i == s.size()) {
            if (cur.empty() && count(address.begin(), address.end(), '.') == 3) {
                ans.push_back(address);
            }
            return;
        }
        if (!cur.empty() && stoi(cur) == 0) return;
        cur.push_back(s[i]);
        if (stoi(cur) > 255) return;
        BT(s, address, cur, i + 1);
        if (address.empty()) {
            BT(s, cur, "", i + 1);
        } else {
            BT(s, address + "." + cur, "", i + 1);
        }
    }
    vector<string> restoreIpAddresses(string s) {
        BT(s);
        return ans;
    }
};

Yen-Chi ChenSat, Jan 21, 2023

Python

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        def BT(address = [int(s[0])], i = 1):
            if i == len(s):
                if len(address) == 4:
                    ans.append('.'.join(map(str, address)))
                return
            old = address[-1]
            new = old * 10 + int(s[i])
            if old != 0 and new <= 255:
                address[-1] = new
                BT(address, i + 1)
                address[-1] = old
            if len(address) < 4:
                BT(address + [int(s[i])], i + 1)
        BT()
        return ans

Yen-Chi ChenSat, Jan 21, 2023

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def check0_255(s):
            x = int(s)
            return x>0 and x<=255

        def dfs(_s, pnts):
            #print('##', _s, pnts)
            if len(_s) > 3*(pnts+1) or len(_s) == 0:
                return []

            if pnts == 0:
                #print('##', pnts, _s, len(_s))
                if len(_s) > 4 or len(_s) == 0:
                    return []
                if _s == '0':
                    return [['0']]
                if _s[0] == '0':
                    return []
                if check0_255(_s):
                    return [ [_s] ]
                return []

            if _s[0] == '0':
                result = []
                for item in dfs(_s[1:], pnts-1):
                    #print(item)
                    result.append( ['0'] + item)
                return result

            
            result = []
            for digit in [1,2,3]:
                x = int( _s[0:digit] )
                #print(pnts, x)
                if check0_255(x):
                    for item in dfs(_s[digit:], pnts-1):
                        #print(pnts, _s, item)
                        result.append( [str(x)] + item)
            #print(pnts, _s, result)
            return result
        
        Q = dfs(s, 3)
        return [ ".".join(x) for x in Q]
        
            

Reference

回到題目列表