题目

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

思路

dfs

代码

class Solution {
    let numRune = [r'0', r'1']
    func dfs(arr: ArrayList<Rune>, ans: ArrayList<String>,n: Int64):Unit{
        if(arr.size >= n){
            ans.insert(0, String(arr))
            // println("insert ${String(arr)}")
            return
        }
        // println("String(arr) = ${String(arr)}")
        for(i in 0..=1){
            // println("for i = ${i}")
            if(i == 0 && arr[arr.size-1] == r'0'){
                // println("continue")
                continue
            }
            var tmparr = ArrayList<Rune>(arr)

            tmparr.insert(arr.size, numRune[i])
            // println("String(tmparr) before dfs = ${String(tmparr)}")
            dfs(tmparr, ans, n)
            // println("String(tmparr) after dfs = ${String(tmparr)}")
        }
        // println("return")
    }
    func validStrings(n: Int64): ArrayList<String> {
        var ans = ArrayList<String>()
        for(i in 0..=1){
            var arr = ArrayList<Rune>()
            arr.insert(arr.size, numRune[i])
            dfs(arr, ans, n)
        }
        return ans
    }
}

复杂度

时间复杂度：O(sizeof(ans))
每个字符位置有0和1两种选择的话是O(2^n)，但是由于做的剪枝，所以相对于全访问，复杂度降低

if(i == 0 && arr[arr.size-1] == r'0'){
                // println("continue")
                continue
            }

空间复杂度：O(n^2)
最深最多保存n个size in 1..n的arr

遇到的坑

1、深浅拷贝问题

var tmparr = ArrayList<Rune>(arr)

如果这一行使用

var tmparr = arr

则在后续修改tmparr的时候，因为是浅拷贝（引用拷贝），因此会直接修改到arr，导致程序出错
n=3时
var tmparr = arr结果

String(arr) = 0
for i = 0
continue
for i = 1
String(tmparr) before dfs = 01
String(arr) = 01
for i = 0
String(tmparr) before dfs = 010
insert 010
String(tmparr) after dfs = 010
for i = 1
String(tmparr) before dfs = 0101
insert 0101
String(tmparr) after dfs = 0101
return
String(tmparr) after dfs = 0101
return
String(arr) = 1
for i = 0
String(tmparr) before dfs = 10
String(arr) = 10
for i = 0
continue
for i = 1
String(tmparr) before dfs = 101
insert 101
String(tmparr) after dfs = 101
return
String(tmparr) after dfs = 101
for i = 1
String(tmparr) before dfs = 1011
insert 1011
String(tmparr) after dfs = 1011
return

var tmparr = ArrayList(arr)结果

String(arr) = 0
for i = 0
continue
for i = 1
String(tmparr) before dfs = 01
String(arr) = 01
for i = 0
String(tmparr) before dfs = 010
insert 010
String(tmparr) after dfs = 010
for i = 1
String(tmparr) before dfs = 011
insert 011
String(tmparr) after dfs = 011
return
String(tmparr) after dfs = 01
return
String(arr) = 1
for i = 0
String(tmparr) before dfs = 10
String(arr) = 10
for i = 0
continue
for i = 1
String(tmparr) before dfs = 101
insert 101
String(tmparr) after dfs = 101
return
String(tmparr) after dfs = 10
for i = 1
String(tmparr) before dfs = 11
String(arr) = 11
for i = 0
String(tmparr) before dfs = 110
insert 110
String(tmparr) after dfs = 110
for i = 1
String(tmparr) before dfs = 111
insert 111
String(tmparr) after dfs = 111
return
String(tmparr) after dfs = 11
return

2、ArrayList 的 insert 位置问题
如果是顺序不敏感的ans，就可以直接在 0 位置插入 String(arr),但是如果是对顺序敏感的arr，则需要插入到队尾，即arr.size,注意不是size-1,相当于end()迭代器的位置
3、Rune(i)使用问题
在一开始写的时候，我尝试过

arr.insert(arr.size, Rune(i))

这样会导致乱码

最后还是

let numRune = [r'0', r'1']
arr.insert(arr.size, numRune[I])

原因： Rune(i) 会使用ascii，i = 0 or 1 的时候不是这个系统可显示字符，因此变口

结果

cangjie