发表于 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 题目链接