[Leetcode]3211. Generate Binary Strings Without Adjacent Zeros

1. 문제 : 

You are given a positive integer n.

A binary string x is valid if all 
substrings
 of x of length 2 contain at least one "1".

Return all valid strings with length n, in any order.

 

Example 1:

Input: n = 3

Output: ["010","011","101","110","111"]

Explanation:

The valid strings of length 3 are: "010", "011", "101", "110", and "111".

Example 2:

Input: n = 1

Output: ["0","1"]

Explanation:

The valid strings of length 1 are: "0" and "1".

 

Constraints:

1 <= n <= 18

 

2. 풀이 : 

첫 번째, backtracking을 이용한 풀이다. backtracking이란 깊이우선탐색으로 하면서 , 내가 원하는 값이 아닐 경우, 가지를 잘라버려 더 이상 그 가지를 탐색하지 않고 부모로 돌아가는 방법이다. 여기서는 조건을 두었다. 마지막값이 0일 경우, 1만 추가해라. + 마지막값이 1인 경우 0과 1 둘 다 추가해라. 따라서, 불필요한 가지에는 접근을 하지 않는다. 

### solution 0 : backtracking
class Solution:
    def validStrings(self, n: int) -> List[str]:
        result = []
    
        def backtrack(current):
            if len(current) == n:
                result.append(current)
                return
            
            if len(current) == 0 or current[-1] == '1':
                backtrack(current + '0')
            
            backtrack(current + '1')
        
        backtrack("")
        return result

 

두 번째, loop를 이용한 풀이다. loop를 이용해서 if 조건문을 이용해 순차적으로 더하는 방식이다. 한 번의 순회가 끝난 다음, 기존에 있던 string들은 제거하는 과정을 거친다. 

### solution 1: loop로 풀이 
class Solution:
    def validStrings(self, n: int) -> List[str]:
        if n == 0:
            return [] 
        count = 1 
        string_list = ["0","1"] 
        while count < n:
            string_list_len = len(string_list)
            count += 1 
            for i in range(string_list_len):
                if string_list[i][-1] == "0" :
                    new_word = string_list[i] + "1" 
                    string_list.append(new_word)
                else:
                    new_word = string_list[i] + "1"
                    string_list.append(new_word)
                    new_word = string_list[i] + "0"
                    string_list.append(new_word)
            for _ in range(string_list_len):
                string_list.pop(0)
        return string_list

 

세 번째, recursion을 이용한 풀이다. 이 풀이는 recursion을 이용해 새로운 리스트를 만들고 거기에 만들어진 string들을 추가하고 , 반환한다. 이때, n-1번째에 있던, string_list에 있는 값을 초기화해주지 않아도 돼서, 간편하기는 하다.

### solution 2 : recursion을 이용한 풀이, memory 절약 x 
class Solution:
    def validStrings(self, n: int) -> List[str]:
        word_list = []
        if n == 0:
            return [] 
        if n == 1:
            return ["0","1"]
        string_list = self.validStrings(n-1) 
        for string in string_list:
            if string[-1] == "0":
                new_word = string + "1"
                word_list.append(new_word) 
            else:
                new_word = string + "0" 
                word_list.append(new_word) 
                new_word = string + "1" 
                word_list.append(new_word)
         
        return word_list

 

네 번째, recursion을 이용한 풀이다. 하지만, 새로운 리스트를 만들지 않고, 기존에 있던 list를 활용해 메모리를 조금 절약할 수 있다. 

### solution3: recursion을 이용한 풀이, memory 좀 더 절약 
class Solution:
    def validStrings(self, n: int) -> List[str]:
        if n == 0:
            return [] 
        if n == 1:
            return ["0","1"]
        string_list = self.validStrings(n-1) 
        string_list_len = len(string_list)
        for i in range(string_list_len):
            if string_list[i][-1] == "0":
                new_word = string_list[i] + "1"
                string_list.append(new_word)
            else:
                new_word = string_list[i] + "0" 
                string_list.append(new_word) 
                new_word = string_list[i] + "1" 
                string_list.append(new_word)
        
        for _ in range(string_list_len):
            string_list.pop(0)
         
        return string_list