JZX轻语：简

LeetCode 3211 - 生成不含相邻零的二进制字符串

发表于2024年08月08日

#回溯法

直接回溯法，如果上一个字符为'0'，则当前字符只能为'1'，否则可以为'0'或'1'。

class Solution:
    def validStrings(self, n: int) -> List[str]:
        ans = []

        def traceback(cur_idx: int, cur_str: str):
            if cur_idx == n:
                ans.append(cur_str)
                return
            traceback(cur_idx + 1, cur_str + '1')
            if cur_str[-1] != '0':  # 上一个字符为'1'，则可以为'0'
                traceback(cur_idx + 1, cur_str + '0')

        traceback(1, '0')
        traceback(1, '1')
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/generate-binary-strings-without-adjacent-zeros