迴文子遞歸解決方案使用全局變量

Question

與遞歸解決方案試圖this：

遞歸我創建的所有子串，並檢查它是否是迴文與否。

問題是我想擺脫全局變量count。

class Solution(object): 
    def countSubstrings(self, s): 
     """ 
     :type s: str 
     :rtype: int 
     """ 
     def palin(s): 
      if s == s[::-1]: 
       return True 
      return False 

     global count 
     count = 0 
     def helper(s, cur, dp): 
      global count 
      ret = 0 
      if cur >= len(s)-1: 
       return 0 
      if cur in dp: 
       return 
      for i in range(cur+1, len(s)): 
       if palin(s[cur:i+1]): 
        count += 1 
        ret = helper(s, i, dp) 
       else: 
        ret = helper(s, i, dp) 
      dp[cur] = ret 
     helper(s, 0, {}) 

     return count + len(s) 

我迄今爲止嘗試：

def helper(s, cur, dp, count): 
     ret = 0 
     if cur >= len(s)-1: 
      return count 
     if cur in dp: 
      return dp[cur] 
     for i in range(cur+1, len(s)): 
      if palin(s[cur:i+1]): 
       ret = helper(s, i, dp, count + 1) 
      else: 
       ret = helper(s, i, dp, count) 
     dp[cur] = ret 
     return dp[cur] 

Answer 1

只需將您的count變量在遞歸helper功能（並根據需要增加）。

Answer 2

你可以做一個新的Counter類，讓您的計數

class Counter: 
    def __init__(self): 
     self.count = 0 

    def __add__(self,num): 
     self.count+=num 
     return self 

的音軌，然後修改代碼以使用計數器

class Solution(object): 
def countSubstrings(self, s): 
    """ 
    :type s: str 
    :rtype: int 
    """ 
    def palin(s): 
     if s == s[::-1]: 
      return True 
     return False 


    def helper(s, cur, dp,count): #make a parameter for Counter 
     ret = 0 
     if cur >= len(s)-1: 
      return 0 
     if cur in dp: 
      return 
     for i in range(cur+1, len(s)): 
      if palin(s[cur:i+1]): 
       count+=1 
       ret = helper(s, i, dp,count) #pass in the Counter 
      else: 
       ret = helper(s, i, dp,count) #pass in here as well 
     dp[cur] = ret 

    a = Counter() #Change here 
    helper(s, 0, {},a) #Change here 

    return a.count + len(s) #Change here 

您設計您的計數和遞歸的方式，你有別無選擇，只能使用可變對象來跟蹤計數。當然，還有更好的方法可以針對這個問題進行遞歸。

Answer 3

這裏是儘可能多的遞歸一個版本，我能想到的（包括您palin綜合徵功能）：

class Solution(object): 
    def countSubstrings(self, s): 
     """ 
     :type s: str 
     :rtype: int 
     """ 
     def palin(s): 
      """recursively checks if bookends match on narrower substrings""" 
      if len(s) <= 1: 
       return True 
      else: 
       # checks if bookends match and inner substring is a palindrome 
       return (s[0] == s[-1]) & palin(s[1:-1]) 

     def first_char_palin_count(s): 
      """counts palindromes of all substrings with first char (pos 0) 
       e.g. will check: "abba", "abb", "ab", "a", "" in palin() 
      """ 
      if len(s) <= 0: 
       return 0 
       # if s is palindrome + shorter palindromes with first char 
      else: 
       return palin(s) + first_char_palin_count(s[:-1]) 

     def helper(s): 
      """counts palindromes in all substrings""" 
      if len(s) <= 0: 
       return 0 
      else: 
       # first char palindromes + palindromes not including first char 
       return first_char_palin_count(s) + helper(s[1:]) 

     return helper(s) 

注意：

• 我需要在我的遞歸2個功能：
  • 一個處理包含第一個字符的所有子字符串（調用本身）
  • 另一個（稱爲helper匹配你的）來處理所有子（有和沒有第一個字符）
• 我並不需要通過任何東西，但周圍的子串（不計數變量全局或局部！），因爲遞歸隱含地表示其所有子問題（在這種情況下爲子串）的結果。