python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 모두 신의가 부족해 보이지만 전체적으로 말하자면 문제의 질은 괜찮으니 한번 해 볼 만하다.
제목
숫자로 구성된 문자열을 지정합니다. 이 문자열을 통해 모든 유효한 IP 주소의 조합을 얻을 수 있기를 바랍니다.유효한 IP 주소에 대해 말하자면, 그것은 4개의 숫자로 구성되어야 하며, 각 숫자의 범위는 0에서 255 사이이다.
하나의 문자열은 여러 개의 IP 주소로 바뀔 수 있으며, 우리는 모든 성립할 수 있는 상황을 저장해야 한다.
예제
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
풀다
이 문제의 뜻은 매우 참신하다. 문자열과 IP 주소를 결합시켰다. 그러나 문제의 핵심은 솔직히 말하면 어떤 것은 흔히 말하는 것이다. 모두 하나의 큰 국면을 약간의 작은 국면의 합으로 바꾸는 상황이다.
우리가 이전에 한 모든 배열 문제, 8황후 문제 등은 모두 이렇다. 8황후 문제를 예로 들면 우리가 바둑판에 황후를 놓아야 하는 것 같다.그러나 실제로 우리가 최종적으로 원하는 결과는 여덟 명의 황후를 방치한 후의 국면이다. 이 국면은 모든 황후를 방치한 후의 작은 국면을 조합하여 구성한 것이다.그래서 본질적으로는 작은 국면을 큰 국면으로 조립하는 문제로 볼 수 있다.
이렇게 많이 말했는데 사실은 단지 한 가지 설명하기 위해서이다. 바로 이런 큰 국면에서 작은 국면을 나누는 문제에 부딪히면 우리가 먼저 검색 알고리즘을 고려할 수 있다.검색 알고리즘은 하나의 검색 공간이나 검색 트리에서 해를 찾는 것으로 이해할 수 있을 뿐만 아니라, 작은 국면을 찾을 수 있는 조합으로 이해할 수 있으며, 그것들을 조합하면 우리가 원하는 큰 국면을 구성할 수 있다.
이 문제에 적용하면 마지막으로 우리가 원하는 큰 국면은 합법적인 IP 주소이고 이 큰 국면을 구성하는 작은 국면은 IP 주소를 구성하는 모든 숫자이다.
이것들을 모두 알아낸 후에 코드는 매우 쓰기 쉽다.

class Solution:
  def restoreIpAddresses(self, s: str) -> List[str]:
    n = len(s)
    if n < 4 or n > 12:
      return []
    
    ret = []
    
    def dfs(cur, ips):
      #  ， ips 4 ip
      #  
      if cur >= n:
        if len(ips) == 4:
          ret.append('.'.join(ips[:]))
        return
      
      #  ip 
      for i in range(cur, min(cur+3, n)):
        #  1 0， 
        if s[cur] == '0' and i > cur:
          return
        # ip 255
        num = int(s[cur: i+1])
        if num > 255:
          return
        
        #  
        ips.append(s[cur: i+1])
        dfs(i+1, ips)
        ips.pop()
        
    dfs(0, [])
    return ret

총결산
새로운 아이디어가 있지만 사고방식의 규칙적인 검색 문제는 dfs를 익히고 거슬러 올라가면 어렵지 않다.
오늘의 문장은 여기까지 끝났습니다. 본문을 좋아하신다면 소질 3연렬로 저에게 약간의 지지를 주십시오.
이상은python 입력 문자열로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)에 대한 상세한 내용입니다. 더 많은python IP 주소 생성에 대한 자료는 저희 다른 관련 글을 주목해 주십시오!