C++LeetCode 구현(93.IP 주소 복원)

[LeetCode]93.IP 주소 복원 IP 주소
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
이 문 제 는 IP 주 소 를 복원 하 는 것 이다.IP 주 소 는 우리 에 게 낯 설 지 않다.설령 우리 가 CS 를 배 운 것 이 아니 더 라 도 우리 가 많은 네티즌 중 한 명 이 라면 낯 설 지 않 아야 한다.IP 주 소 는 32 비트 2 진수 로 구성 되 어 사용 하기 편리 하도록 XXX.XXX.XXX.XXX.XXX 형식 으로 표현 되 며 각 그룹의 XXX 는 255 의 10 진수 보다 작 거나 같 음 을 나타 낸다.그래서 IP 주 소 는 모두 4 단 이 고 한 단락 에 한 명,두 명 또는 세 명 이 있 을 수 있 습 니 다.범 위 는[0,255]입 니 다.문 제 는 입력 문자열 에 숫자 만 포함 되 어 있다 는 것 을 명확 하 게 밝 혔 습 니 다.그래서 한 단락 이 세 자리 일 때 우 리 는 경 계 를 넘 었 는 지 판단 해 야 합 니 다(>255).그리고 중요 한 것 은 한 사람 만 있 을 때 0 은 한 단락 이 될 수 있 습 니 다.두 분 또는 세 분 이 있 을 때 00,01,001 과 같 습 니 다.011,000 등 은 모두 비합법적 이기 때문에 우 리 는 어떤 문자열 이 합 법 적 인지 판단 하 는 판정 함수 가 필요 하 다.이 문 제 는 문자열 의 세그먼트 문제 라 고 볼 수 있 습 니 다.입력 문자열 에 세 개의 점 을 추가 하고 문자열 을 네 단락 으로 나 누 며 모든 가능 한 상황 을 합 법 적 으로 구 해 야 합 니 다.현재 이렇게 많은 문 제 를 해결 한 결과 두 가지 경험 을 얻 었 다.하 나 는 문자열 의 하위 서열 이나 배합 문제 에 부 딪 히 면 동적 계획 DP 를 먼저 고려 하 는 것 이 고,다른 하 나 는 가능 한 모든 상황 을 구하 기 위해 재 귀 를 먼저 고려 하 는 것 이다.이 문 제 는 문자열 의 하위 서열 이나 배합 문 제 를 구 하 는 것 이 아니 라 두 번 째 상황 에 더욱 부합 되 기 때문에 우 리 는 재 귀적 으로 풀 어야 한다.우 리 는 k 로 현재 나 누 어야 할 단락 수 를 표시 합 니 다.만약 k=0 이 라면 세 개의 점 이 이미 가입 되 었 고 네 단락 이 형성 되 었 음 을 표시 합 니 다.만약 에 이때 문자열 이 비어 있 으 면 현재 나 누 어 진 결 과 를 저장 합 니 다.만약 k!=0.각 단락 에 대해 우 리 는 각각 한 명,두 명,세 명 으로 시도 하여 합 법 적 인지 아 닌 지 를 판단 합 니 다.만약 에 합 법 적 이면 재 귀 를 통 해 남 은 문자열 을 계속 나 누고 최종 적 으로 모든 합 법 적 인 조합 을 구 합 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        restore(s, 4, "", res);
        return res;
    }
    void restore(string s, int k, string out, vector<string> &res) {
        if (k == 0) {
            if (s.empty()) res.push_back(out);
        }
        else {
            for (int i = 1; i <= 3; ++i) {
                if (s.size() >= i && isValid(s.substr(0, i))) {
                    if (k == 1) restore(s.substr(i), k - 1, out + s.substr(0, i), res);
                    else restore(s.substr(i), k - 1, out + s.substr(0, i) + ".", res);
                }
            }
        }
    }
    bool isValid(string s) {
        if (s.empty() || s.size() > 3 || (s.size() > 1 && s[0] == '0')) return false;
        int res = atoi(s.c_str());
        return res <= 255 && res >= 0;
    }
};

우리 도 isValid 함 수 를 줄 일 수 있 습 니 다.재 귀 를 호출 하기 전에 if 문 구 를 사용 하여 문제 의 뜻 에 부합 되 지 않 는 상황 을 거 를 수 있 습 니 다.이 안에 k 를 사 용 했 습 니 다!=std::to_string(val).size()는 사실 이해 하기 어렵 지 않 습 니 다.예 를 들 어 k=3 일 때 설명 은 세 자리 수 여야 합 니 다.그러나 문자 가'010'이 라면 정형 val=10 으로 바 꾸 고 문자열 을 되 돌 리 는 것 은'10'입 니 다.이때 의 길이 와 k 값 이 다 르 면 요구 에 맞지 않 는 상황 을 찾 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
C++해법 2:

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        helper(s, 0, "", res);
        return res;
    }
    void helper(string s, int n, string out, vector<string>& res) {
        if (n == 4) {
            if (s.empty()) res.push_back(out);
        } else {
            for (int k = 1; k < 4; ++k) {
                if (s.size() < k) break;
                int val = atoi(s.substr(0, k).c_str());
                if (val > 255 || k != std::to_string(val).size()) continue;
                helper(s.substr(k), n + 1, out + s.substr(0, k) + (n == 3 ? "" : "."), res);
            }
        }
    }
};

자바 해법 2:

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        helper(s, 0, "", res);
        return res;
    }
    public void helper(String s, int n, String out, List<String> res) {
        if (n == 4) {
            if (s.isEmpty()) res.add(out);
            return;
        }
        for (int k = 1; k < 4; ++k) {
            if (s.length() < k) break;
            int val = Integer.parseInt(s.substring(0, k));
            if (val > 255 || k != String.valueOf(val).length()) continue;
            helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3 ? "" : "."), res);
        }
    }
}

각 단락 의 숫자 는 최대 세 자리 만 있 을 수 있 고 네 단락 으로 나 눌 수 있 기 때문에 상황 이 많 지 않다.우 리 는 폭력 적 으로 검색 하 는 방법 을 사용 할 수 있다.각 단락 은 1 에서 3 까지 순환 한 다음 에 4 단락 의 숫자 가 원래 문자열 의 길이 와 같 을 때 우 리 는 각 단락 의 숫자 가 255 보다 크 지 않 은 지 판단 한 다음 에 요구 에 맞지 않 는 숫자 를 거 르 고 결과 에 넣 으 면 된다.코드 는 다음 과 같 습 니 다.
C++해법 3:

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        for (int a = 1; a < 4; ++a) 
        for (int b = 1; b < 4; ++b) 
        for (int c = 1; c < 4; ++c) 
        for (int d = 1; d < 4; ++d) 
            if (a + b + c + d == s.size()) {
                int A = stoi(s.substr(0, a));
                int B = stoi(s.substr(a, b));
                int C = stoi(s.substr(a + b, c));
                int D = stoi(s.substr(a + b + c, d));
                if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
                    string t = to_string(A) + "." + to_string(B) + "." + to_string(C) + "." + to_string(D);
                    if (t.size() == s.size() + 3) res.push_back(t);
                }
            }
        return res;
    }
};

자바 해법 3:

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        for (int a = 1; a < 4; ++a) 
        for (int b = 1; b < 4; ++b) 
        for (int c = 1; c < 4; ++c)
        for (int d = 1; d < 4; ++d) 
            if (a + b + c + d == s.length()) {
                int A = Integer.parseInt(s.substring(0, a));
                int B = Integer.parseInt(s.substring(a, a + b));
                int C = Integer.parseInt(s.substring(a + b, a + b + c));
                int D = Integer.parseInt(s.substring(a + b + c));
                if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
                    String t = String.valueOf(A) + "." + String.valueOf(B) + "." + String.valueOf(C) + "." + String.valueOf(D);
                    if (t.length() == s.length() + 3) res.add(t);
                }
            }
        return res;
    }
}

C++구현 LeetCode(93.복원 IP 주소)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++복원 IP 주소 내용 은 저희 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 읽 어 주시 기 바 랍 니 다.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!