LeetCode (C/C++, Java) 93. Restore IP Addresses

https://leetcode.com/problems/restore-ip-addresses/description/

---

풀이

문자열을 앞에서부터 1~3자리로 나누면서 나뉜 값의 범위가 (0, 255)인지 확인 후, 주소 형태의 문자열로 만드는 과정을 반복한다.

주어진 문자열이 4개로 나뉘거나, 문자열을 다 사용했을 때의 조건을 확인해 답 배열에 추가해준다.

---

C/C++ 코드

class Solution {
public:
    vector<string> addresses;
    void getIP(string s, int cnt, string ip) {
        
        if (cnt == 4 || s.empty()) {
            // 4개로 나뉘어짐 && 주어진 문자열을 다 사용함
            if (cnt == 4 && s.empty())
                addresses.push_back(ip.substr(0, ip.size() - 1));
            else
                return;
        }

        // 현재 원소가 0이라면 무조건 1개만 사용 가능함
        if (s[0] == '0') {
            return getIP(s.substr(1), cnt + 1, ip + "0.");
        }
    
        // 1~3자리로 나눴을 때 수의 범위가 (0, 255)라면 삽입
        for (int i = 0; i < min(3, (int)s.size()); i++) {
            string sub = s.substr(0, i + 1);
            if (0 <= stoi(sub) && stoi(sub) <= 255)
                getIP(s.substr(i + 1), cnt + 1, ip + sub + ".");
        }
    }

    vector<string> restoreIpAddresses(string s) {
        getIP(s, 0, "");
        return addresses;
    }
};

 

Java 코드

class Solution {
    public List<String> answer = new ArrayList<>();

    public void getIPs(String s, StringBuilder ip, int cnt) {
        if (s.isEmpty() || cnt == 4) {
            if (s.isEmpty() && cnt == 4) {
                ip.setLength(ip.length() - 1);
                answer.add(ip.toString());
            }
            return;
        }

        if (s.charAt(0) == '0') {
            getIPs(s.substring(1), ip.append("0."), cnt + 1);
            return;
        }

        for (int i = 0; i < Math.min(3, s.length()); i++) {
            int subInt = Integer.parseInt(s.substring(0, i + 1));
            int len = ip.length();
            if (0 <= subInt && subInt <= 255) {
                getIPs(s.substring(i + 1), ip.append(subInt).append("."), cnt + 1);
                ip.setLength(len);
            }
        }
    }
    public List<String> restoreIpAddresses(String s) {
        getIPs(s, new StringBuilder(), 0);
        return answer;
    }
}