Algorithm Problem Sharing: Given a string consisting of "0", "1" and "?", where "?" can be replaced with 0 or 1, find all possible results.

I came across an interesting problem today that wasn't on LeetCode or online, so I wrote one myself and wanted to share it with you all.

topic

Given a string consisting of "0", "1", and "?", where "?" can be replaced with either 0 or 1, find all possible results.

example:

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

answer

This is a fairly standard permutation and combination problem, so I won't go into the thought process; I'll just show you the answer.

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)