Algorithm Question Sharing: Given a string, consisting of "0", "1" and "?" Composition, where "?" It can be replaced with 0 or 1 for all possible results

今天看到了一个比较有意思的题，发现leetcode上没有，网上也没参考答案，所以自己写了个和大家分享下。

题目

给定一个字符串，由“0”，“1”和“?”组成，其中“?”可以替换成0或1，求所有可能的结果

例子：

• • “0” => [“0”]
  • “?” => [“0”, “1”]
  • “0?” => [“00”, “11”]
  • “??” => [“00”, “01”, “10”, “11”]

解答

比较常规的排列组合题目了，不说思路了，直接看答案。

class solution:

    def replace(self,string):

        result = []
        self.dfs(string,0,"",result)
        
        return result

    def dfs(self,string,pos,curr,result):
        
        if pos == len(string):
            result.append(curr)

        while pos < len(string) and string[pos] != "?":
            curr += string[pos]
            pos += 1

        if pos == len(string):
            result.append(curr)
        else:
            self.dfs(string,pos+1,curr + "0",result)
            self.dfs(string,pos+1,curr + "1",result)