Julia实现回溯问题

综合讨论区
1

在遇到力扣题目LC 131时，写了以下代码，结构和python的是一致的，但在python下运行的结果和julia下的不同，代码如下：

function partition(s::AbstractString)
    n = length(s)
    is_parlindrom = fill(true, n, n)

    for i in n:-1:1, j in (i + 1):n
        is_parlindrom[i, j] = (s[i] == s[j]) && is_parlindrom[i + 1, j - 1]
    end

    res = Vector{Vector{String}}()
    p = String[]

    function dfs!(i::Int)
        if i == n + 1
            push!(res, p)
            @info res
            return
        end

        for j in i: n
            if is_parlindrom[i, j]
                push!(p, SubString(s, i, j))
                dfs!(j + 1)
                pop!(p)
            end
        end
    end

    dfs(1)

    return res
end

输出如下：

julia> partition("aab")
[ Info: [["a", "a", "b"]]
[ Info: [["aa", "b"], ["aa", "b"]]
2-element Array{Array{String,1},1}:
 []
 []

一直搞不懂，为啥res变量在中间有存到值，但最后返回不出来，是哪里出错了？

2

这题我已经Commit了 :dog:

3

嗯我看到了，但我俩的回溯部分写法不同，我还是想知道我这种错在哪里 :joy:

4 
julia> let
           res = Vector{Vector{String}}()
           p = ["a", "b"];
           push!(res, p)
           pop!(p)
           res
       end
1-element Vector{Vector{String}}:
 ["a"]

julia> res[1] === p
true
5

可是python也会出现这样的情况呀……

In [1]: res = []

In [2]: p = [1, 2, 3]

In [3]: res.append(p)

In [4]: p.pop()
Out[4]: 3

In [5]: res
Out[5]: [[1, 2]]
6

Python的时候用的p[:]， 我大概知道问题出在哪了，所以push!(res, p)的时候是把p传引用了，没有传值

7

我把push!(res, p)改成push!(res, p[:])后代码就运行正常了。。我一直以为在没有@view的情况下都是copy version的。非常感谢！！

8

切片才会有copy

1 个赞