LeetCode #93. Restore IP Addresses 해설

해설

 

준비과정.

• 백트래킹 알고리즘을 위해 IP를 구성하는 부분의 숫자를 저장할 self.path 를 준비한다.
• IP의 리스트를 담을 self.result 를 준비한다.
• IP에 찍히는 "."의 수를 기록할 변수 self.pointNum 을 준비한다.
• backtracking 함수를 준비한다.

 

백트래킹이 끝나는 조건 (종결조건) 정하기.

• 백트래킹이 끝나는 조건은 마침표 "."의 수가 3개일 때, (이 경우 이미 IP의 형식이 완성되었기 때문이다.)
• 그리고 인풋으로 들어간 숫자가 유효할 때 끝낸다.
• + 그리고 뒤에서 보겠지만, backtracking 함수는 마침표 "."가 찍히는 이전 숫자까지만 self.path에 넣는 성향을 보인다. 그렇기에 이 종결조건 안에 마지막 요소의 숫자도 넣어주는 함수를 넣어주어 self.result에 넣는다.
• self.result에 넣었으면 다시 마지막 요소를 빼주어서 다음 백트래킹에 문제가 없도록 해준다.

 

백트래킹 알고리즘 정하기.

• IP의 각각의 요소(255.255.255.10의 경우 255 또는 10을 말한다.)가 유효한 숫자인지 판단하고 self.path에 넣는다.
• 그리고 마침표 "." 수를 하나 더한다.
• 유효하다면 거기서 다음 순서부터 다시 backtracking을 돌려 다음 유효한 요소를 self.path에 넣기 위한 백트래킹을 진행한다.
• 백트래킹을 나오고 나선 바로 이전에 넣은 요소를 다시 빼고,
• 마침표 "." 수도 하나 줄여준다.

 

필터링 조건.

• 인풋으로 들어간 숫자의 길이가 4개보다 작거나 12개보다 크면 바로 함수를 종료한다. 
• 시작 index가 끝 index 보다 클 경우 말이 안되므로 False 를 출력한다.
• 시작 숫자가 "0"인데 그 숫자가 한자리 숫자가 아닐 경우 False를 출력한다.
• 숫자가 아닌 문자일 경우 False를 출력한다.
• 해당 숫자 요소가 255보다 클 경우 False를 출력한다.
• 그 외의 경우는 숫자 요소가 문제가 없다는 의미이므로 True를 출력한다.

 

 

코드

from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.pointNum=0

    def restoreIpAddresses(self, s: str) -> List[str]:
        # terminate condition
        if (len(s) < 4) or (len(s)>12):
            return self.result
        
        self.backtracking(s, 0)
        return self.result


    def backtracking(self, s, startIndex):
        
        # terminate condition: there are 3 dots and the numbers are valid
        if (self.pointNum == 3):
            # check validity
            if (self.isValid(s, startIndex, len(s)-1)):
                # only if it is true, add it in result
                self.path.append(s[startIndex:])
                self.result.append(".".join(self.path))
                self.path.pop()
            return

        for i in range(startIndex, len(s)):
            # check validity of each numbers
            if (self.isValid(s, startIndex, i)):
                self.pointNum += 1
                self.path.append(s[startIndex:i+1])
                self.backtracking(s, i+1)
                self.path.pop()
                self.pointNum -= 1
            else:
                break

    # Filtering unvalid numbers
    def isValid(self, s, startIndex, endIndex) -> bool:
        # if the number is not one, and the first number is 0
        if startIndex > endIndex:
            return False
        
        if (s[startIndex]=="0") and (endIndex != startIndex):
            return False

        # if the number is not numbers
        for i in range(startIndex, endIndex+1):
            if (s[i]<"0") or (s[i]>"9"):
                return False
        
        # if the number is larger than 255
        if (int(s[startIndex:endIndex+1])>255):
            return False
        
        return True
    
aa = "25525511135"
aa = "0000"
aa = "101023"
sol = Solution()
print(sol.restoreIpAddresses(aa))