[Leetcode]3211. Generate Binary Strings Without Adjacent Zeros

문제 요약

• 알고리즘 분류: 재귀호출
• 난이도: Medium
• 문제내용:
  • 문자열 길이 n이 있다.
  • 문자열에는 0과 1만 올수 있다.
  • 0뒤에는 1만 올 수 있다.
• 사이트 주소: https://leetcode.com/problems/generate-binary-strings-without-adjacent-zeros/description/

문제풀이

 이번 문제는 간단한 재귀호춣 구현이다. 구현은 아래와 같이 하면된다.

1. 끝에 숫자가 1일때만 0추가하고 재귀호출한다.
2. 뒤에 1을 추가하고 재귀호출한다.
3. 문자열길이가 n일때 리스트에 추가한다.

 재귀호출 기본적인 문제라서 문제 푸는데는 어렵지 않다. 위에 처럼 구현 하면 시간 복잡도는 O(2^n)만큼 나온다.

Code

Python

class Solution:
    def validStrings(self, n: int) -> List[str]:
        result = []
        # 재귀함수
        def recursion(s: str):
            if len(s) == n:
                result.append(s)
                return

            # 뒤에 1이면 0을 추가한다.
            if(len(s) == 0 or s[-1] == '1'):
                recursion(s + '0')
            recursion(s + '1')

        recursion("")
        return result

Java

class Solution {
     List<String> result;
    int length;

    public List<String> validStrings(int n) {
        result = new ArrayList<>();
        length = n;
        recursion( "");
        return result;
    }

    /*
     * 재귀 호출 함수
     */
    public void recursion( String s){
        if(s.length() == length){
            result.add(s);
            return;
        }

        // 끝에 숫자가 1일때 뒤에 0을 추가 한다.
        if(s.isEmpty() || s.charAt(s.length() - 1) == '1'){
            recursion( s + '0');
        }
        recursion( s + '1');

    }
}