Medium

题目描述

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的子字符串都至少包含一个 “1”，那么 x 就是有效的。

返回所有长度为 n 的有效字符串，可以以任意顺序返回。

示例 1：

输入：n = 3
输出：["010","011","101","110","111"]
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输入：n = 1
输出：["0","1"]
解释：
长度为 1 的有效字符串有："0" 和 "1"。

提示：

  • 1 <= n <= 18

提示信息：

  • 如果我们有一个长度为 x 的字符串 s，我们可以生成所有长度为 x + 1 的字符串。
  • 如果 s 的最后一个字符是 0，我们只能添加 1；而如果最后一个字符是 1，我们可以添加 0 和 1。
  • 我们可以使用递归和回溯来生成所有这样的字符串。

解题思路

这道题要求生成不含相邻零的二进制字符串，本质上是一个约束条件下的字符串生成问题。

核心约束分析：

  • 任意长度为 2 的子字符串都至少包含一个 “1”
  • 这意味着不能有连续的 “00” 出现

解法一：递归回溯（推荐） 从左到右构建字符串，每次决定当前位置放 ‘0’ 还是 ‘1’：

  • 如果前一位是 ‘0’，当前位只能是 ‘1’（避免 “00”）
  • 如果前一位是 ‘1’，当前位可以是 ‘0’ 或 ‘1’
  • 递归到长度为 n 时，将结果加入答案

解法二：动态规划思路 可以用 DP 思想：dp[i][0] 表示长度为 i 且以 ‘0’ 结尾的字符串数量，dp[i][1] 表示以 ‘1’ 结尾的数量。但由于需要输出所有字符串，回溯更直接。

时间复杂度： 每个有效字符串都会被生成一次，总数约为斐波那契数列的值，所以是 O(φⁿ)，其中 φ 是黄金比例。

代码实现

class Solution {
public:
    vector<string> validStrings(int n) {
        vector<string> result;
        string current;
        backtrack(n, current, result);
        return result;
    }
    
private:
    void backtrack(int n, string& current, vector<string>& result) {
        if (current.length() == n) {
            result.push_back(current);
            return;
        }
        
        // 如果当前字符串为空或者最后一个字符是 '1'，可以添加 '0'
        if (current.empty() || current.back() == '1') {
            current.push_back('0');
            backtrack(n, current, result);
            current.pop_back();
        }
        
        // 总是可以添加 '1'
        current.push_back('1');
        backtrack(n, current, result);
        current.pop_back();
    }
};

class Solution:
    def validStrings(self, n: int) -> List[str]:
        result = []
        
        def backtrack(current):
            if len(current) == n:
                result.append(current)
                return
            
            # 如果当前字符串为空或者最后一个字符是 '1'，可以添加 '0'
            if not current or current[-1] == '1':
                backtrack(current + '0')
            
            # 总是可以添加 '1'
            backtrack(current + '1')
        
        backtrack('')
        return result

public class Solution {
    public IList<string> ValidStrings(int n) {
        var result = new List<string>();
        var current = new StringBuilder();
        Backtrack(n, current, result);
        return result;
    }
    
    private void Backtrack(int n, StringBuilder current, IList<string> result) {
        if (current.Length == n) {
            result.Add(current.ToString());
            return;
        }
        
        // 如果当前字符串为空或者最后一个字符是 '1'，可以添加 '0'
        if (current.Length == 0 || current[current.Length - 1] == '1') {
            current.Append('0');
            Backtrack(n, current, result);
            current.Remove(current.Length - 1, 1);
        }
        
        // 总是可以添加 '1'
        current.Append('1');
        Backtrack(n, current, result);
        current.Remove(current.Length - 1, 1);
    }
}

/**
 * @param {number} n
 * @return {string[]}
 */
var validStrings = function(n) {
    const result = [];
    
    function backtrack(current) {
        if (current.length === n) {
            result.push(current);
            return;
        }
        
        // Always can add '1'
        backtrack(current + '1');
        
        // Can add '0' only if last character is not '0'
        if (current.length === 0 || current[current.length - 1] === '1') {
            backtrack(current + '0');
        }
    }
    
    backtrack('');
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(φⁿ)，其中 φ ≈ 1.618 是黄金比例，有效字符串的数量遵循斐波那契数列规律
空间复杂度O(n × φⁿ)，需要存储所有有效字符串，每个字符串长度为 n，递归栈深度为 O(n)

相关题目