91. Decode Ways (Medium)

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.

class Solution:
    def numDecodings(self, s: str) -> int:

        if  not s: return 0
        n = len(s)
        dp = [0]*(n+1)
        dp[0] = 1 # empty string has 1 way
        dp[1] = 1 if s[0]!='0' else 0 #single char can not have leading 0

        for i in range(2,n+1):
            #      cur
            # pre  cur
            cur = int(s[i-1])
            precur = int(s[i-2:i])

            if 1<=cur<=9:
                dp[i]+=dp[i-1]
            
            if 26>=precur>=10:
                dp[i]+=dp[i-2]
            
        return dp[-1]
      

试图用递归+mem方法写，越写越繁琐。。。没有解决。 看答案用了DP。
解决方法很巧妙。 空字符dp val=1， dp【1】为首字符结果， 如果首字符为0，则dp【1】=0 else dp【1】=1 从字符第二位到末位。 检查cur 和 （per，cur）形成的数字。 如果valid。就做dp【i】的更新。

92. Reverse Linked List II （Medium）

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        
        def rev(node):
            pre=None
            while node :
                nodenext=node.next
                node.next = pre
                pre=node
                node = nodenext    
            return pre
        
        # get left~right chan, do rev, concat
        
        dummyhead=ListNode(val='NULL',next=head)
        
        cur = dummyhead
        pre=None
        for _ in range(left):
            pre=cur
            cur = cur.next
        
        revhead_pre=pre
        revhead=cur
        
        for _ in range(right-left):
            cur=cur.next

        revend = cur
        revend_next = revend.next
        revend.next = None
        
        revhead_pre.next=rev(revhead)
        revhead.next = revend_next
        
        return dummyhead.next
##
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
 
        dummyhead = ListNode(val = 'NULL',next=head)
        cur = dummyhead
        
        A = None
        for _ in range(left):
            A = cur
            cur =cur.next
        B = cur
        pre = None
        for _ in range(right-left+1):
            curnext = cur.next
            cur.next = pre
            pre = cur
            cur = curnext

        A.next = pre
        B.next = cur
        return dummyhead.next

用了dummyhead 细心就可以了。。。

93. Restore IP Addresses （Medium）

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 4 parts, 0 ~ 255 
        ss = s
        
        res = []
        
        def bt(s,tmp):
             
            if len('.'.join(tmp))==len(ss)+3 and len(tmp)==4:
                res.append('.'.join(tmp))
                
            for length in [1,2,3]:
                if len(s)>=length and 255>=int(s[:length])>=0:
                    if (length==2 or length==3) and s[0]=='0' : continue
                    tmp.append(s[:length])
                    bt(s[length:],tmp)
                    tmp.pop()
        
        bt(s,[])
        
        return res
###
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        def bt(tmp, s):
            if len(tmp)==4 and not s:
                res.append('.'.join(tmp))
                return 
            if s and 9>=int(s[0])>=0:
                bt(tmp+[s[0]],s[1:])
            if len(s)>1 and int(s[0])!=0 and 99>=int(s[:2])>=1:
                bt(tmp+[s[:2]],s[2:])
            if len(s)>2 and int(s[0])!=0 and 255>=int(s[:3])>=100:
                bt(tmp+[s[:3]],s[3:])
        
        bt([],s)
        return res             

backtracking 终止条件是被分割成4份而且总长度是string长度加3个点长度。 可能的length只有1，2，3。 length 2，3时候0不能作为开头元素。

94. Binary Tree Inorder Traversal （Easy）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        res = []
        def ino(node):
            if not node: 
                return
            ino(node.left)
            res.append(node.val)
            ino(node.right)
        
        ino(root)
        return res

递归很容易写，how about iterative one？

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        res = []
        s = []
        while s or root:
            while root:
                s.append(root)
                root = root.left
            
            node = s.pop()
            res.append(node.val)
            
            if node.right:
                root =node.right
        
        return res

经典写法了应该是，当stack有东西或者root不为空，root先入栈，一直探索左子树。当root为空时。从stack中取出node，提取值。如果有右子树。则开始以右子树的node作为root探索。

95. Unique Binary Search Trees II （Medium）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        
        nums = list(range(1,n+1))
        
        def gen(nums):
            if not nums:
                return [None]
            res = []
            for i in range(len(nums)):
                mid = nums[i]
                leftnums=nums[:i] if i!=0 else []
                rightnums = nums[i+1:] if i!=len(nums)-1 else []
                
                for left in gen(leftnums):
                    for right in gen(rightnums):
                        root = TreeNode(mid)
                        root.left = left
                        root.right= right
                        res.append(root)
            
            return res
        
        return gen(nums)

递归分治法。

96. Unique Binary Search Trees （Medium）

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

class Solution:
    mem = {0:1,1:1,2:2}
    def numTrees(self, n: int) -> int:
        if n in self.mem: return self.mem[n]
        if n==0:
            return 1
        if n==1:
            return 1
        if n==2:
            return 2
        
        res= 0
        for i in range(n):
            left = i
            right= n-left-1
            res += self.numTrees(left)*self.numTrees(right)
        self.mem[n]=res
        return res
#
class Solution:
    def numTrees(self, n: int) -> int:
        @lru_cache(None)
        def cal(n):
            if n==0: return 1
            if n==1: return 1
            res = 0
            for left in range(n):
                right = n-left-1
                res+=cal(left)*cal(right)
            return res
        
        return cal(n)

递归+记忆 比较容易理解。 答案是什么catalanta number，不感兴趣。。

97. Interleaving String （Medium）

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        
        #dp[i][j]   i is length of string1   
        #           j is length of string2
        #           so interleaving length= i+j
        
        
        
        m=len(s1)
        n=len(s2)
        
        if m+n!=len(s3) or sorted(s1+s2)!=sorted(s3):
            return False
        
        dp=[ [False]*(n+1) for _ in range(m+1)]
        dp[0][0]=True
        
        #fill row 0
        for col in range(1,n+1):
            dp[0][col]=dp[0][col-1] and s2[col-1]==s3[0+col-1]
        #fill col 0
        for row in range(1,m+1):
            dp[row][0]=dp[row-1][0] and s1[row-1]==s3[0+row-1]
            
        #dp
        
        for row in range(1,m+1):
            for col in range(1,n+1):
                dp[row][col]=(dp[row-1][col] and s1[row-1]==s3[row+col-1] ) or (dp[row][col-1] and s2[col-1]==s3[row+col-1])
        
        return dp[m][n]
        

没思路。。。
思路： dynamic programming dp[i][j] 是指长度为i的s1和长度为j的s2是否可interleave。所以dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
没想到是dynamic programming， 最小子结构是差一位时候，是否interleaving有递推关系。

98. Validate Binary Search Tree （Medium）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        s = []
        pre=None
        while s or root:
            while root:
                s.append(root)
                root=root.left
                
            node = s.pop()
            if pre is not None:
                if pre>=node.val:
                    return False
                
            pre = node.val
            
            if node.right:
                root=node.right
        return True

可以inorder 然后看是否递增，或者iterative的inorder 直接判断。

99. Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
 
        s=[]
        y=x=pre=None

        while s or root:
            while root:
                s.append(root)
                root=root.left
           
            node=s.pop()
            
            if pre and pre.val> node.val:
                y=node
                if x is None:
                    x=pre
                else:
                    break
           
            pre=node
            if node.right:
                root=node.right
            
        x.val,y.val=y.val,x.val

很巧妙的解法， 如果x是None， 第一次记录下pre>cur中的pre node, 第二次记录下 pre>cur中的cur node。 【1，2，3，4，5，6】交换2，5 【1，5，3，4，2，6】 第一次出现pre>cur 时候，pre就是5，第二次出现pre>cur时候 cur 是2. 这样就找到了需要交换的nodes。

100. Same Tree （Easy）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        
        if not p:
            return not q
        
        if not q:
            return not p
        
        return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)