在一个 leetcode 问题中在 DFS 中工作的奇怪方式

Question

我认为这只是 Python 函数和数据结构的一些根本区别，但我无法弄清楚为什么方法 II 不起作用它似乎变量 res 也在期间更改值遍历但不符合预期，谁能告诉我为什么。

方法一：

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        n=len(tiles)
        d={}
        for e in tiles:
            d[e]=d.get(e,0)+1
            
        s=''
        res=[0]   ## only difference
        self._help(d,s,res,n)
        return res[0]
        
    def _help(self,d,s,res,n):

        if len(s)<n:
            for e in d:
                if d[e]>0:
                    d[e]-=1
                    res[0]+=1
                    print(s)
                    print(res)
                    self._help(d,s+e,res,n)
                    d[e]+=1

方法二：

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        
        n=len(tiles)
        d={}
        for e in tiles:
            d[e]=d.get(e,0)+1
            
        s=''
        res=0
        self._help(d,s,res,n)
        return res 0
        
    def _help(self,d,s,res,n):

        if len(s)<n:
            for e in d:
                if d[e]>0:
                    d[e]-=1
                    res+=1
                    print(s)
                    print(res)
                    self._help(d,s+e,res,n)
                    d[e]+=1

Answer 1

您在第一个中传递一个数组，第二个是 int。

这会简单地通过：

class Solution:
    def numTilePossibilities(self, tiles):
        frequencies = collections.Counter(tiles)
        product = 1
        for f in frequencies.values():
            product *= -~f

        possibles = 0
        for num in range(1, product):
            digits = []
            for f in frequencies.values():
                digits.append(num % -~f)
                num //= -~f
            temp = math.factorial(sum(digits))
            for digit in digits:
                temp //= math.factorial(digit)
            possibles += temp

        return possibles

class Solution:
    def numTilePossibilities(self, tiles):
        frequencies = collections.Counter(tiles)
        product = 1
        for f in frequencies.values():
            product *= (f + 1)

        possibles = 0
        for num in range(1, product):
            digits = []
            for f in frequencies.values():
                digits.append(num % -~f)
                num //= (f + 1)
            temp = math.factorial(sum(digits))
            for digit in digits:
                temp //= math.factorial(digit)
            possibles += temp

        return possibles

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

在一个 leetcode 问题中在 DFS 中工作的奇怪方式

strange way of working in DFS in one of leetcode questions

python

permutation

letter

mutable

depth-first-search

参考资料