求助一个google的高频电面题目!

求助一个google的高频电面题目，有点被自己绕晕了！求大侠指点
balanced String 只能有 0 和 1，不能有连续3个位置上数字相同的string.
1.给定长度n，一共有多少种balanced string
2.给定长度n, 生成所有给定长度的string

如果用DFS的话，可能这样做吧？两个问题只是这个res的形式不一样

def balanced_string(n):
    res = []
   
    def dfs(pref):
        if len(pref) >= 3 and (pref[-3:] == '111' or pref[-3:] == '000'):
            return

        if len(pref) == n:
            res.append(pref)
            return

        for i in ['0', '1']:
            pref += i
            dfs(pref)
            pref = pref[:-1]

    dfs('')
    return res

我也提供一个思路吧，就算数的

dp的话就是 dp[n] = 2*dp[n-1] - dp[n-3]

可能比较容易理解一点，就是把所有长度为n-1的符合条件的str后面加0或者加1，会得到2*dp[n-1]这么多的str，但是里面有一些是不符合条件的，就把它们减掉，这些不符合条件的str出现三个连续的0或1的地方只会在最后三位，一半是000，另一半是111，一共有dp[n-3]这么多个

算出来的结果和dp[n] = dp[n-1] + dp[n-2]是一样的

写成代码是
def dp(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n == 2:
        return 4
    elif n == 3:
        return 6
    else:
        return 2*dp(n-1) - dp(n-3)

drift1981 发表于 2019-10-5 06:43
我自己照这个方法写了一下，终止条件需要再加一个 len(pref) > n，大牛一定是写忘记了，非常感谢！

实在不敢当。没想通，所以想问一下，为什么要加这个check呢？按理说，不会有>n的情况出现的吧。不过我确实忘记了一个特殊的输入情况，就是n = 0的时候，应该在程序最开始的时候check一下。

dp 感觉是这样
n[i][1] = n[i - 1][0] + n[i - 1][1] - n[i - 2][1]
n[i][0] = n[i - 1][1] + n[i - 1][0] - n[i - 2][0]

return n[n][0] + n[n][1]

提供个思路，用dp，dp**[i] 表示endwith**，长度为i的string的数量，例如dp00[i] 就是endwith 00，并且长度为i

dp00[i] = dp10[i - 1];
dp01[i] = dp00[i - 1] + dp10[i - 1];
dp10[i] = dp11[i - 1] + dp01[i - 1];
dp11[i] = dp01[i - 1];

yiliaobailiao 发表于 2019-10-5 06:06
如果用DFS的话，可能这样做吧？两个问题只是这个res的形式不一样

def balanced_string(n):

非常感谢牛人的指导！

yiliaobailiao 发表于 2019-10-5 06:06
如果用DFS的话，可能这样做吧？两个问题只是这个res的形式不一样

def balanced_string(n):

我自己照这个方法写了一下，终止条件需要再加一个 len(pref) > n，大牛一定是写忘记了，非常感谢！

pengpengcode 发表于 2019-10-5 06:17
dp 感觉是这样
n[1] = n[0] + n[1] - n[1]
n[0] = n[1] + n[0] - n[0]

谢谢！我去实现一下。

SimonLevy 发表于 2019-10-5 06:20
提供个思路，用dp，dp** 表示endwith**，长度为i的string的数量，例如dp00 就是endwith 00，并且长度为i

...

谢谢提供思路！我去实现一下。

DP:
F[n] = F[n-1] + F[n-2]
F[1] = 2
F[2] = 4

Set F[n][0] is the number of strings with length n ending with 0, F[n][1] is ending with 1.
So: F[n][0] = F[n-1][1] + F[n-2][1], F[n][1] = F[n-1][0] + F[n-2][0]
as F[n] = F[n][0] + F[n][1]
F[n] = F[n-1] + F[n-2]


补充内容 (2019-10-6 00:55):
    def gen_zero_ones(self, n):
        result = []

        def dfs(k, tmp, result):
            if k == 0:
                result.append(tmp)
                return
            if len(tmp) >= 2 and tmp[-1] == tmp[-2]:
                t = "1" if tmp[-1] == "0" else "0"
                dfs(k - 1, tmp + t, result)
            else:
                dfs(k - 1, tmp + "0", result)
                dfs(k - 1, tmp + "1", result)

        dfs(n, "", result)
        return result