leetcode_190_contest

5416. 检查单词是否为句中其他单词的前缀

思路：
直接遍历数组，取前缀匹配满足的第一个字符串即可。前缀匹配可自己手写或直接用接口。

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        res = -1
        for i, word in enumerate(sentence.split(' ')):
            if word.startswith(searchWord):
                res= i+1
                break
        return res

5417. 定长子串中元音的最大数目

思路：
维护滑动窗口中的元音字母数量即可。可先对字符串预处理标记，为元音字母的标记为1，否则为0。遍历窗口的右侧端点，直接对出滑动窗口的端点进行进出操作即可，体现为代码就是对应位置的加减标记操作。

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        tmp = [0] * len(s)
        for i,x in enumerate(s):
            if x in ('a','e','i','o','u'):
                tmp[i] = 1
        res= sum(tmp[:k])
        t_sum = res
        for i in range(k,len(s)):
            t_sum -= tmp[i-k]
            t_sum += tmp[i]
            res = max(res, t_sum)
        return res

5418. 二叉树中的伪回文路径

思路：
容易想到，深度优先搜索记录路径上的所有节点，但结合题目回文串的特点，可以使用计数器来进行记录。
判断能够构成回文串，如果所有字符的个数都是偶数个或者仅一个字符个数是奇数个，肯定可以构成。如果有两个及两个以上的字符是奇数个，无法构成回文串。
至此，递归深搜即可。

# 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

from collections import Counter
class Solution:
    def __init__(self):
        self.counter =Counter()
        self.res = 0
        
    def judge(self):
        flag = False
        for x,val in self.counter.items():
            if val % 2 == 1:
                if not flag:
                    flag=True
                else:
                    return 
        self.res += 1
        
        
    def dfs(self,root):
        if root is None:
            return
        self.counter[root.val] += 1
        if root.left is None and root.right is None:
            # 对叶节点进行判断
            self.judge()
            self.counter[root.val] -= 1
            return 
        self.dfs(root.left)
        self.dfs(root.right)
        self.counter[root.val] -= 1
        
            
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        self.dfs(root)
        return self.res

5419. 两个子序列的最大点积

思路：
本题对序列的顺序有要求，很容易联想到最长公共子序列等经典DP问题。然后进一步思考，状态表示$dp[i][j]$ 标识两个序列截止位置i和位置j的最大点击。
状态转移：因为对序列点击的顺序有要求，可以根据最后一个位置是否参与点击来进行状态集合的切分，又由于求最大值，所有不必要求切分的时候每个集合严格不重复，只需要保证情况不遗漏即可。

$$\begin{equation} \begin{split} dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], dp[i-1][j-1]+ \\ nums1[i] \times nums2[j], nums1[i]\times nums2[j]) \end{split} \end{equation}$$

可以看到max函数中囊括了所有的可能情况，注意不要遗漏的情况是$nums1[i]*nums2[j]$这一种情况，即不考虑前面序列的点积只取当前结尾的两个数字的点积。

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n= len(nums2)
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # print(dp)
        dp[0][0] = nums1[0] * nums2[0]
        res = dp[0][0]
        for i in range(1,m):
            dp[i][0] = max(dp[i-1][0], nums1[i]*nums2[0])
            res = max(res,dp[i][0])
        for j in range(1,n):
            dp[0][j] = max(dp[0][j-1], nums1[0]*nums2[j])
            res= max(res,dp[0][j])
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+nums1[i]*nums2[j])
                dp[i][j] = max(dp[i][j], nums1[i]*nums2[j])
                res = max(res,dp[i][j])
        return res