Leetcode 458 补题

Leetcode 458

用特殊操作处理字符串 II

对于给定的数据范围显然不能暴力求解，考虑反向处理操作序列。记录最终的字符串长度，倒序遍历操作序列，如果k(从0开始)大于等于字符串长度那么越界无解。

• 当操作是删除时，递归处理前n-1个操作，同时字符串长度加一，因为k在前面，删除末尾字符不会影响到前面，即使后面的操作可能会反转，但因为是递归处理所以k的位置早已变化；
• 当操作是反转时，改变k为对称位置，再递归处理前n-1个操作；
• 当操作是复制时，如果k在右半边，那么就移动到左半边，再递归处理前n-1个操作；
• 如果是字符，且此时k等于字符串长度-1(偏移)，说明找到了答案，反之递归处理前n-1个操作；

class Solution:
    def processStr(self, s: str, k: int) -> str:
        sz=0
        # 记录最终长度
        for r in s:
            if r=='#':sz*=2
            elif r=='*':
                if sz:sz-=1
            elif str.isalpha(r):sz+=1
        # 递归处理
        def dfs(n,k,sz):
            # 不存在
            if k>=sz or not n:return '.'
            c=s[n-1]
            if c=='*':
                return dfs(n-1,k,sz+1)
            elif c=='#':
                # 在右半边
                if k>=sz//2:return dfs(n-1,k-sz//2,sz//2) 
                return dfs(n-1,k,sz//2)
            # 反转
            elif c=='%':return dfs(n-1,sz-k-1,sz)
            else:
                if k==sz-1:return c
                return dfs(n-1,k,sz-1)
        return dfs(len(s),k,sz)

图中的最长回文路径

直接爆搜显然是不行的，回文串的做法就几种，考虑使用中心扩展法优化，枚举回文中心，这样就只需往两边找相同的字符。

由于节点个数较少因此可以使用状态压缩记录操作过的节点，定义dp(x,y,s)为左右端点为x,y的回文串，s记录已选过的节点，去枚举x,y的相邻节点做状态转移

max=lambda x,y:x if x>y else y

class Solution:
    def maxLen(self, n: int, edges: List[List[int]], nums: str) -> int:
        ans=1 # 只有一个节点的情况
        # 建图
        g=[[] for _ in range(n)]
        for u,v in edges:
            g[u].append(v)
            g[v].append(u)
        @cache
        def dp(x,y,s):
            res=0
            # 枚举
            for nx1 in g[x]:
                if s>>nx1&1:continue
                for nx2 in g[y]:
                    # 需要字符相同，且没选过
                    if nx1!=nx2 and s>>nx2&1==0 and nums[nx1]==nums[nx2]:
                        # 注意要保证相对顺序，否则会多出很多重复状态
                        if nx1>nx2:nx1,nx2=nx2,nx1
                        res=max(res,2+dp(nx1,nx2,s|(1<<nx1)|(1<<nx2)))
            return res  
        
        for u,v in edges:
            # 单个点作为中心
            ans=max(ans,1+dp(u,u,(1<<u)))
            ans=max(ans,1+dp(v,v,(1<<v)))

            # 两个点作为中心
            if nums[u]==nums[v]:
                if u>v:u,v=v,u
                ans=max(ans,2+dp(u,v,(1<<u)|(1<<v)))
        return ans