3211. Generate Binary Strings Without Adjacent Zeros / TypeScript

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".

 

출처 : https://leetcode.com/problems/generate-binary-strings-without-adjacent-zeros/

 

풀이 

function validStrings(n: number): string[] {
    let gen=[];
    let result=[];

    function dfs(i,prev){
        if(i==n){
            result.push(gen.join(''));
            return;
        }
        if(prev!='' && prev=='0'){
            gen.push('1');
            dfs(i+1,'1');
            gen.pop();

        }else{
            gen.push('0');
            dfs(i+1,'0');
            gen.pop();

            gen.push('1');
            dfs(i+1,'1');
            gen.pop();
        }
    }

    dfs(0,'');
    return result;
};

 

주어진 숫자 n에 따라 특정 규칙을 따르는 문자열 배열을 생성.

"0"과 "1"로 이루어진 문자열을 생성하는데, "0"이 연속으로 나오지 않도록 하는 함수

 

 

예제

입력: n = 3

이 경우 함수는 길이가 3인 문자열 중에서 연속된 "0"이 없는 모든 가능한 문자열을 생성

함수 동작 과정

1. 초기 상태:
   • gen = []
   • result = []
2. dfs(0, '') 호출:
   • i = 0, prev = ''
   • prev가 빈 문자열이므로 "0"과 "1" 모두 추가 가능.
3. "0" 추가:
   • gen = ['0']
   • dfs(1, '0') 호출.
4. dfs(1, '0'):
   • i = 1, prev = '0'
   • 이전 문자가 "0"이므로 "1"만 추가 가능.
5. "1" 추가:
   • gen = ['0', '1']
   • dfs(2, '1') 호출.
6. dfs(2, '1'):
   • i = 2, prev = '1'
   • "0"과 "1" 모두 추가 가능.
7. "0" 추가:
   • gen = ['0', '1', '0']
   • dfs(3, '0') 호출.
8. dfs(3, '0'):
   • i = 3, prev = '0'
   • i가 n과 같으므로, gen을 문자열로 변환하여 result에 추가.
   • result = ['010']
   • "0" 제거:
   • gen = ['0', '1']
9. "1" 추가:
   • gen = ['0', '1', '1']
   • dfs(3, '1') 호출.
10. dfs(3, '1'):
    • i = 3, prev = '1'
    • i가 n과 같으므로, gen을 문자열로 변환하여 result에 추가.
    • result = ['010', '011']
    • "1" 제거:
    • gen = ['0', '1']
11. "1" 제거:
    • gen = ['0']
    • "0" 제거:
    • gen = []

 

 

 gen.push('0');
 dfs(i+1,'0');
 gen.pop();

함수 끝

---

 

 gen.push('1');
 dfs(i+1,'1');
 gen.pop();
 
함수 시작

1. "1" 추가:
   • gen = ['1']
   • dfs(1, '1') 호출.
2. dfs(1, '1'):
   • i = 1, prev = '1'
   • "0"과 "1" 모두 추가 가능.
3. "0" 추가:
   • gen = ['1', '0']
   • dfs(2, '0') 호출.
4. dfs(2, '0'):
   • i = 2, prev = '0'
   • "1"만 추가 가능.
5. "1" 추가:
   • gen = ['1', '0', '1']
   • dfs(3, '1') 호출.
6. dfs(3, '1'):
   • i = 3, prev = '1'
   • i가 n과 같으므로, gen을 문자열로 변환하여 result에 추가.
   • result = ['010', '011', '101']
   • "1" 제거:
   • gen = ['1', '0']
   • "0" 제거:
   • gen = ['1']
7. "1" 추가:
   • gen = ['1', '1']
   • dfs(2, '1') 호출.
8. dfs(2, '1'):
   • i = 2, prev = '1'
   • "0"과 "1" 모두 추가 가능.
9. "0" 추가:
   • gen = ['1', '1', '0']
   • dfs(3, '0') 호출.
10. dfs(3, '0'):
    • i = 3, prev = '0'
    • i가 n과 같으므로, gen을 문자열로 변환하여 result에 추가.
    • result = ['010', '011', '101', '110']
    • "0" 제거:
    • gen = ['1', '1']
11. "1" 추가:
    • gen = ['1', '1', '1']
    • dfs(3, '1') 호출.
12. dfs(3, '1'):
    • i = 3, prev = '1'
    • i가 n과 같으므로, gen을 문자열로 변환하여 result에 추가.
    • result = ['010', '011', '101', '110', '111']
    • "1" 제거:
    • gen = ['1', '1']
13. "1" 제거:
    • gen = ['1']
    • "1" 제거:
    • gen = []

최종 결과

함수는 연속된 "0"이 없는 길이 3의 문자열을 모두 생성하여 반환

['010', '011', '101', '110', '111']