我们在写某些字符串问题上经常需要用到一些基础架构, 当然你可以选择直接暴力。一般，我会选择一些效率够高的函数模板,因为你需要多次调用。以下是我总结的几个关于常用的字符串操作模板:

判断x是否为y的子序列:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = j = 0
        while i < len(s) and j < len(t):
            if t[j] != s[i]:
                j += 1
            else:
                i += 1
                j += 1
        return i == len(s)

可应用在这道题上,具体代码为:

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        strs.sort(key= len, reverse=True)
        def isSubsequence(s: str, t: str) -> bool:
            i = j = 0
            while i < len(s) and j < len(t):
                if t[j] != s[i]:
                    j += 1
                else:
                    i += 1
                    j += 1
            return i == len(s)
        for i, x in enumerate(strs):
            # for j, y in enumerate(strs):
            #     if i != j and isSubsequence(x, y):
            #         break
            # else: 
            #     return len(x)
            if all(i==j or not isSubsequence(x, y) for j,y in enumerate(strs)):
                return len(x)
        return -1

最长递增子序列

# 贪心 + 二分, 时间复杂度O(nlogn)
def lengthOfLIS(self, nums: List[int]) -> int:
        g=[]
        for x in nums:
            j=bisect_left(g, x)
            if j==len(g):
                g.append(x)
            else:
                g[j]=x
        return len(g)