PYTHON_STUDY DFS combination and permutation and graph

DFS == backtracking !!!(递归返回后镜像撤销递归前加入到数据!!!) 
1 problem find missing number:
Giving a string with number from 1-n in random order, but miss 1 number.Find that number.
def dfs(self, n, str, result, visit_set, count):
        if len(str) == 0 and count == n-1:
            return result
        
        elif count < n - 1:
            for i in range(len(str)):
                if int(str[:i+1]) >= 1 and int(str[:i+1]) <= n and int(str[:i+1]) not in visit_set and str[0] != '0':
                    visit_set.add(int(str[:i+1]))
                    res = self.dfs(n, str[i+1:], result - int(str[:i+1]), visit_set, count+1)
                    if res != None:
                        return res
                    visit_set.remove(int(str[:i+1])) -- 镜像撤销
                    
        return None
            
    """
    @param n: An integer
    @param str: a string with number from 1-n in random order and miss one number
    @return: An integer
    """
    def findMissing2(self, n, str):
        # write your code here
        result = sum(range(1,n+1))
        return self.dfs(n, str, result, set(), 0)

2 problem palindrome partition II:
idea: idea : using two dp method to optimize !

def minCut(self, s):
        # write your code here
        #first DP table to store if substring is palindrome
        dp_table = [[True for j in range(len(s))] for i in range(len(s))]
        for l in range(2, len(s)+1):
            for i in range(len(s)-l+1):
                j = i + l - 1
                if s[i] == s[j] and dp_table[i+1][j-1] == True:
                    dp_table[i][j] = True
                else:
                    dp_table[i][j] = False
        #second dp table to store the minimum cut of substring
        result = [0 for i in range(len(s))]
        for i in range(1, len(s)):
            if dp_table[0][i] == False: #if is palindrome, cut remains zero
                result[i] = math.inf
                for j in range(1, i+1):
                    if dp_table[j][i] == True: #since j->i is palindrome, result is cut from 0 to j-1 plus 1 !!
                        result[i] = min(result[i], result[j-1] + 1)
                    
        return result[-1]

problem subsets using 1/0 method of DFS: meaning we either choose current element as part of each combination or not !

def dfs(self, nums, idx, temp_result, result):
        if idx == len(nums):
            result.append(temp_result)
        elif idx < len(nums):
            self.dfs(nums, idx+1, temp_result+[nums[idx]], result)
            self.dfs(nums, idx+1, temp_result, result)
        return
    
    """
    @param nums: A set of numbers
    @return: A list of lists
    """
    def subsets(self, nums):
        # write your code here
        result = []
        if nums == None:
            return result
        nums.sort()
        self.dfs(nums, 0, [], result)
        return result

problem remove invalid parenthese using dp-combination based analogy to subsets II(duplicated element):
note:in order to find the minimum modification seqs, we calculate relative number of left brackets and right brackets
instead of absolute number like count_brackets does !!!

def count_brackets(self, s):
        left, right = 0, 0
        for char in s:
            if char == "(":
                left += 1
            elif char == ")":
                if left > 0:
                    left -= 1
                else:
                    right += 1
        return left, right
        
def check_valid(self, s):
        left, right = 0, 0
        for char in s:
            if char == "(":
                left += 1
            elif char == ")":
                right += 1
            if right > left:
                return False
        return left == right
        
 def dfs(self, s, left, right, idx, results): #idx is used to prevent duplicated(avoid looking back)
        if left == 0 and right == 0 and self.check_valid(s) == True:
            results.append(s)
            return
        for i in range(idx, len(s)):
            if s[i] == "(" or s[i] == ")":
                if i > idx and s[i-1] == s[i]: #avoid duplicated solutions
                    continue
                if left > 0 and s[i] == "(":
                    self.dfs(s[:i]+s[i+1:], left - 1, right, i, results)
                if right > 0 and s[i] == ")":
                    self.dfs(s[:i]+s[i+1:], left, right - 1, i, results)
        return

problem word break using on-dimensional DP table:

    def wordBreak(self, s, dict):
        # write your code here
        dp_table = [False for i in range(len(s)+1)] #dp_table[i] stores check result indicating if s[:i] is wordbreakable !!!
        dp_table[0] = True #empty is always to be true !!
        maxlen = self.getmaxlen(dict)
        for i in range(1, len(s)+1):
            for j in range(min(maxlen, i)+1):
                if dp_table[i-j] == True and s[i-j:i] in dict:
                    dp_table[i] = True
                    break
        return dp_table[-1]
        
    follow up of workbreak iii:find number of ways to break string s
    
    def wordBreak3(self, s, dict):
        # Write your code here
        dp_table_bool, dp_table_num = [False for i in range(len(s)+1)], [0 for i in range(len(s)+1)]
        #dp_table_bool stores result if substring[:i] is wordbreakable from dict;dp_table_num stores number of ways to break
        
        dp_table_bool[0], dp_table_num[0] = True, 1 #initial states
        maxlen = self.getmaxlen(dict)
        temp = set()
        for word in dict:
            temp.add(word.lower())
            temp.add(word)
        dict = temp
        s = s.lower()
        for i in range(1, len(s)+1):
            for j in range(min(maxlen, i)+1):
                if dp_table_bool[i-j] == True and s[i-j:i] in dict:
                    dp_table_bool[i] = True
                    dp_table_num[i] += dp_table_num[i-j]
        return dp_table_num[-1]
        
problem: word break II using both dp method for bottom-up and memorization top-down approach:
memorization top-down:
def dfs(self, s, wordset, mem_table):
        if s in mem_table.keys():
            return mem_table[s]
        
        results = []
        
        if s in wordset:
            results.append(s)
        
        for idx in range(len(s)-1, 0, -1):
            if s[idx:] in wordset:
                segs = self.dfs(s[:idx], wordset, mem_table)
                for sol in segs:
                    results.append(sol + " " + s[idx:])
        
        mem_table[s] = results
        
        return results
     
bottom-up dp solution:
    def getmaxlen(self, dict):
        result = 0
        for word in dict:
            result = max(result, len(word))
        return result
        
    def wordBreak(self, s, wordDict):
        maxlen = self.getmaxlen(wordDict)
        dp_result_table = [[] for i in range(maxlen+1)]

        for i in range(1, len(s)+1):
            dp_result_table[i%(maxlen+1)] = []
            for j in range(1, min(i, maxlen)+1):
                if s[i-j:i] in wordDict:
                    if i == j or len(dp_result_table[(i-j)%(maxlen+1)]) > 0:
                        if i == j:
                            dp_result_table[i%(maxlen+1)].append(s[:i])
                        else:
                            for sol in dp_result_table[(i-j)%(maxlen+1)]:
                                dp_result_table[i%(maxlen+1)].append(sol + " " + s[i-j:i])
                        
        return dp_result_table[len(s)%(maxlen+1)]

permutation based DFS:
if i > 0 and nums[i] == nums[i-1] and ! visited[i]://remove duplicated permutation in DFS !!!
    continue