重庆工程网站建设,网站如何做更新,一个网站如何做推广方案,鸿运通网站建设给你一个正整数 n。
如果一个二进制字符串 x 的所有长度为 2 的
子字符串
中包含 至少 一个 1#xff0c;则称 x 是一个 有效 字符串。
返回所有长度为 n 的 有效 字符串#xff0c;可以以任意顺序排列。 示例 1#xff1a;
输入#xff1a; n 3
输出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。
思路
如果我们有长度为 x 的字符串根据二进制的规则我们就能够生成长度为 x1 的字符串递归调用如果当前字符串以 0 结尾我们只能向后补 1否则出现 00如果以 1 结尾则可以补 0 或 1。
因此我们可以采用递归的思想从长度为 1 的字符串开始生成按照上面的逻辑生成全部长度为 n 的可能结果。 代码C
class Solution {
public:vectorstring validStrings(int n) {vectorstring result;for (char start : {0, 1}) {backtrack(string(1, start), n, result);}return result;}void backtrack(string current, int n, vectorstring result) {if (current.length() n) {result.push_back(current);return;}if (current.back() 0) {backtrack(current 1, n, result);} else {backtrack(current 0, n, result);backtrack(current 1, n, result);}}
}; 代码C 用队列逐层生成字符串
class Solution {
public:vectorstring validStrings(int n) {vectorstring result;queuestring q;q.push(0);q.push(1);while (!q.empty()) {string current q.front();q.pop();if (current.length() n) {result.push_back(current);continue;}if (current.back() 0) {q.push(current 1);} else {q.push(current 1);q.push(current 0);}}return result;}
};
代码Python
class Solution:def validStrings(self, n: int) - List[str]:def backtrack(current):if len(current) n:result.append(current)returnif current[-1] 0:backtrack(current 1)else:backtrack(current 0)backtrack(current 1)result []for start in [0, 1]:backtrack(start)return result
