# leetcode

**Repository Path**: lanjing99/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: 存放leetcode代码
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-11-09
- **Last Updated**: 2021-08-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

[toc]

# 刷题收获

1. 在程序运行前现在大脑中推演结果，不能依赖测试用例来找到错误。写完代码第一件事是停下来思考，检查代码是否没问题，再运行，要养成这样的习惯。
2. 5遍刷题法，做起来又犯懒。
3. 写代码不光是脑力活，也是一种肌肉记忆。有时候，写出来的代码就跟脑袋里想的不一样。可能就是开小差了。



# 刷题记录

## [5] 最长回文子串

1. 从最大子串到小的字符串开始，暴力求解最长的回文子串，超时了。

2. 中心扩展算法，这个算法还是挺好理解的。做起来也比较简单。中心扩展提前剪枝。

3. 动态规划，状态用一个二维数组表示，bool类型的dp\[i][j]，代表字符串str[i...j]是不是一个回文串。 str[i...j] == str[i] == str[j] && dp\[i+1][j-1]。因为i < j，所以规模能够缩小的。

   

## [10] 正则表达式匹配

### 1. 使用递归实现

递归实现想法比较简单，我自己饶了弯路。source字符串和pattern字符串的匹配过程。

从头开始匹配。

如果字符匹配，或者是. 字符

​	下一个字符是否是\"*", 如果是，（这个分支最复杂），匹配source字符串的下一个位置（模拟出现大于1次的情况。）

​	如果不是"\*"，匹配source和pattern的下一个字符。

如果字符不匹配

​	下一个字符是否是\"*"，如果时，从pattern当前位置+1开始匹配，模拟出现次数为0的情况。

​	如果不是\"*"，直接返回false，表明数据不匹配。

这个问题想起来不难，但是代码很不熟练， 大半天才写完，中间又隔了几天。代码还是要有手感。

```swift
func isMatch(source: Array<Character>, sourceIndex: Int,
                 pattern: Array<Character>, patternIndex: Int) -> Bool{
        if sourceIndex == source.count && patternIndex == pattern.count {
            return true
        }
        
        let sourceCharacter = source.safeIndex(index: sourceIndex)
        let patternCaracteer = pattern.safeIndex(index: patternIndex)
        if (sourceCharacter == patternCaracteer || patternCaracteer == ".")
            && sourceCharacter != nil{
            if pattern.isWildCharacterAtIndex(index: patternIndex + 1){
                    return isMatch(source: source, sourceIndex: sourceIndex + 1, pattern: pattern, patternIndex: patternIndex)
                        || isMatch(source: source, sourceIndex: sourceIndex, pattern: pattern, patternIndex: patternIndex + 2)

            }else{
                return isMatch(source: source, sourceIndex: sourceIndex + 1, pattern: pattern, patternIndex: patternIndex + 1)
            }
        }else{
            if pattern.isWildCharacterAtIndex(index: patternIndex + 1){
                return isMatch(source: source, sourceIndex: sourceIndex, pattern: pattern, patternIndex: patternIndex + 2)
            }else{
                return false
            }
        }
    }
```

### 2. 使用动态规划实现



## [17] 电话号码的字母组合

使用递归分治，弄清楚N和N-1的关系，递归起来还是挺容易的。





## [20] 有效的括号匹配

1. 使用栈来实现括号匹配。Python中没看到Stack数据结构，使用List来替代。
2. 增加一个dic来存储括号的对应关系，可以简化代码，增加灵活性。
3. 判断key也从字段中获取数据，进一步简化代码
4. 栈预存一个？能够简化栈是否为空的判断，提高执行效率。速度快过70%变成速度快过94%



## [22] 括号生成

使用递归方式完成，关键是如何将问题拆解成更简单的子问题，这个估计要多做题才能解决。



## [24] 两两交换链表中的节点

用递归很好理解，代码也简单，递归是个强大的工具。



## [36] 有效的数独

按照行，列，9个小格子的判断，比较容易。

格子的判断不是一个格子接着一个格子判断，这样循环不好写，而且按照行列的顺序，对应到一个numberSet\[3][3]里的set进行判断



## [42] 接雨水
1. 暴力解法，找每个位置可以存放的水是多少。找到左右边界。在此基础上存储每个位置的左右边界最大值能将时间复杂度从O(n^2)编程O(n).
2. 使用栈解法
   1. 单调递减的栈很好用。
   2. 弄清楚做边界和右边界与面积的关系
3. 使用双向指针法：根据暴力解法，使用双指针来求解。假设右边有一堵很高的强。左边要怎样才能存水？要看左边边界的高度和当前位置的高度。当前位置比较矮，就能存水，否则当前位置会变成左边新的墙。



## [45] 跳跃游戏 II

1. 在55题的基础上很容易能想到解法。
2. 最短路径想到层次遍历，想到队列，数组中原本就有队列。



## [46] 全排列
1. 全排列的终止条件： 只剩一个元素为加入排列
2. n和n-1的关系。 遍历n，取出每个元素，加上剩余的所有排列组合的可能。
3. 有大量的数组删除和拷贝操作，可能可以优化。
4. 感觉递归操作效率不低，但是Python数组复制怎么没影响效率，有点奇怪。



## [47] 全排列 II
1. 在[46]的全排列的基础上，利用Set去重。可以实现，不是个好策略。用时528ms，击败10.53%
2. 在排列之前提前剪枝，极大提高了效率， 48ms， 94.74%
3. 在源头消除重复，而不是用set去重



## [49] 字母异位词分组

先对字符串排序，再放到字典里比较。

要注意的是，Python字典的使用跟 其它语言不一样，字典获取不存在的value会抛出错误。

存到字典里的值也是一个引用类型的值，不是值类型的



## [50] Pow(x, n)

1. 用最简单的循环迭代超时了，复杂度是O（n)
2. 用折半迭代，复杂度是log（n）
3. 注意一下Python取整除是 //



## [51] N 皇后

1. 使用遍历方法求解，每一个合法的下一个位置，如果当前位置可以放皇后，开始下一行，如果不可以放，递增下一列。昨天花了3.5个小时理解这个题目。边界条件的调试花了2个小时。
2. 使用dfs方式求解。边界条件不用判断了，就是[0, n)，利用递归去展开条件判断。不用自己傻傻的计算。不用半个小时代码就写好了。当前位置能够放皇后再进行下一次递归，不能的话就可以提前结束。dfs方式代码更简单，效率更高，也更好理解。



## [52] N皇后 II

在51题的基础上做这题很容易



## [55] 跳跃游戏

1. 贪心算法，没跳过去的话，返回到上一级。这个方法超时了，没想到更好的方法。这个跳不过去的时候要测试的情况太多了。

2. 看题解的收获，感觉就是一步一步往前拱，贪心算法？



## [62] 不同路径

1. 直接用递归会超时。
2. 使用带存储中间状态的递归，注意m，n，行和列的关系。

---

1. 使用迭代而不是带存储状态的方法实现，效率会提高很多。
2. 核心新观察到下面的递推公司

```python
pathsCount[j] = pathsCount[j+1] + pathsCount[j]
```



## [63] 不同路径 II

1. 在[62]的基础上，判断一个obstacle的状态，比较容易。

---

用迭代方式做，好几个地方出错了

1. 初始化的时候，默认值应该为0，从右向左，如果没有障碍再初始化为1
2. 最右列，如果有一个位置上有障碍，也要赋值为0



## [64] 最小路径和
1. 主要算法理解起来简单，但是细节的地方错了两次，用了半个小时的时间调试。
2. 初始化results的时候，计算column出错。results的作用一开始没想明白。



## [69] x 的平方根

1. 用折半查找实现，注意0，1边界条件。
2. **折半查找下一次的取值应该是mid - 1，或者mid + 1， 不应该再取mid，因为已经比较过了**
3. 在运行之前自己先试试，不能依赖测试代码验证。



## [72] 编辑距离

1. 用递归可以实现，但是因为存在重复计算，所以会超时。

2. 用动态规划实现，关键是找到状态转移方程

   ```swift
   if firstCharacters[i-1] == secondCharacters[j-1] {
   	dp[i][j] = dp[i-1][j-1]
   }else{
     dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
   }
   ```

   



## [74] 搜索二维矩阵

1. 折半查找，理解起来很容易，审题的时候有点没搞清楚。
2. 计算row和column，column计算错了，写成了mid % rowCount，既然没发现，调试了十几分钟。还是有点自以为是，不去确认细节。

```python
row = mid // columnCount
column =  mid % columnCount
```



## [77] 组合
这个解法现在没搞懂。。

1. 弄清楚 N 和 N-1 之间的关系，这里要求的组合是不重复的。返回条件是k==1的时候
2. 注意小标， startIndex从1开始，而不是从0， 判断条件是tartIndex <= n - count + 1， 用特殊值试一下。例如4 2



2. 使用递归解法，如何将问题N分解成N-1。这个组合规模N可以分解为
   1. 取第一个数，从剩下的去k-1个数
   2. 不取第一个数，从生下的取k个数。



## [78] 子集

这一题理解了递归之后比较容易，遍历每个元素，每个元素只有两种状态，有或者没有



## [84] 柱状图中最大的矩形

1. 使用遍历高度的解法，算法复杂度O(n^2)，最后两个用例超时了。要注意查找左边和右边高度的边界情况。

2. 使用栈的方式来解决

   1. 思考一下左边界和右边界，分别是比当前值小的时候。

   2. 维护一个有序栈，当前值比栈顶值大的时候，入栈。当前值比栈顶值小，说明栈顶值的右边界已经到了，左边界是上一个元素。这样就能计算矩形的宽度了。

   3. 当栈不为空（多于一个元素）的时候，要继续处理。

   4. 注意[0],[1], 这种边界情况的处理。

      

## [91] 解码方法
1. 用递归，0的判断条件不好实现。从后往前推推不下去。
2. 0的判断有点麻烦，这个题目需要重新看。边界条件比较麻烦。



## [94] 二叉树的中序遍历

1. 使用递归方法实现 （确实比较简单）

   - Your runtime beats 43.47 % of python3 submissions
   - Your memory usage beats 9.32 % of python3 submissions (13.5 MB)

2. 使用栈迭代方法

   - Your runtime beats 87.43 % of python3 submissions
   - Your memory usage beats 88.27 % of python3 submissions (13.3 MB)

   python列表为空时，返回false，这是个语法糖的功能，不太严谨。

   ```python
   while p or stack:
               while p:
                   stack.append(p)
                   p = p.left
               top = stack.pop()
               result.append(top.val)
               p = top.right
   ```



## [98] 验证二叉搜索树

1. 递归实现比较容易，关键是将一个节点的最小值和最大值想清楚。画一个树出来，然后用纸和笔推演几步。
2. 传3个参数就够了，当前结点，当前节点的最小值和最大值。父节点不需要传。



非递归实现，带状态

1. 遍历的结构和前序遍历一致

2. 要注意的是min和max的额外状态每一层都不同，要入栈。进入下一级的时候，如何更新min和max

   

## [102] 二叉树的层序遍历

二叉树的层次遍历用队列实现，比较简单，这个题目的难度系数应该为简单，不应该是中等。



## [105] 从前序与中序遍历序列构造二叉树
1. 递归算法，找到规模N和N-1的关系。确定根节点，列出左子树和右子树，递归实现比较容易。
2. 考虑输入为空数组的边界情况，这个一直没做。
3. 通过前序遍历找到跟结点，中序遍历找左右结点，这里递归的条件找中序结点的下标需要用到上一次的结果，所以用Swift 嵌套函数捕获preorderIndex变量，不使用成员变量。
4. 算法想清楚了，不代表代码就能写对。犯了两个错误，map应该存的是inorder的下标，而不是preorder的下标。 preorderIndex 索引在获取子树的根节点索引之后，划分左右子树之前 + 1. 详见代码。 
5. **在写下代码的那一刻就要保证正确，而不是写完，提交，遇到错误再修改**。这样对、编写代码的能力是上不去的。



## [106] 从中序与后序遍历序列构造二叉树

1. 解法1：使用递归，先利用后续找到root，再根据中序区分左子树和右子树。
2. 解法2：使用迭代。
   1. 原理和[105]类似，但是下标索引还是超出两次
   2. 注意左右边界，右边界指向数组最后一个元素的下一个位置。也就是array.cout
   3. 和[105]不同的是，这里应该先构建右子树。感觉做了两道题，把可能犯错的地方都犯了。



## [107] 二叉树的层次遍历 II

1. Swift Array 是个值类型，有时候也挺麻烦的，要先取出数组，修改，然后再复制改回去 (可以用inout参数啊)
2. level信息当做参数来传递



## [122] 买卖股票的最佳时机 II

1. 每天把能挣到的钱都挣了，总共的利润就是最大的。这可不就是贪心吗？：D
2. 能用贪心算法的话，就会发现贪心算法往往是最简单也是最优的，难的地方在于怎么发现是可以贪心的，怎么贪心。
3. 代码运行了3次才把题做对，我没有一次就做对的意识。嗯，从现在起开始做。



## [125] 验证回文串

1. 脑袋里想到的逻辑和写出来的代码要保持一致，在细节上犯错误就调试起来就浪费时间。写完代码第一件事不是运行代码，而是先检查一遍代码。



## [126] 单词接龙 II

在127的基础上解题。

127只需要找出一条路径，而本题找出所有的最短路径。最短路径还是使用层次遍历。但每个节点增加一个数组来存放父节点。

当生成路径时。根据这些父节点信息生成路径，并且去除虚拟节点。

在127的基础上，这题确实难，从想明白到写清楚花了我186m，以不好好学习前欠的债终究是要还的，没关系，我现在一个个过，不求虚假的多，而求实际掌握的内容，哪怕很少，很是可以坚实依赖的。

## [127] 单词接龙

1. 解法1：**超时** ，用树的结构做，每次从单词列表中提取相差为1的词，这个会超时。时间复杂度O(n^2)，这个太高了。思路似乎没错。
2. 解法2：巧妙构建一个图，将word设置成节点，只差一个单词的词语设置成虚拟节点，节点放到dict里，生成图的复杂度就降低了一个数量级。最后用图的层次遍历解决最短路径问题。以前没写过图的代码，都只是看懂，距离会写代码还是有很远的距离的。这个题目花了我286分钟，算是补以前的课，值得。



## [144] 二叉树的前序遍历

1. 解法1：递归调用版本挺容易实现的， 代码也很简洁。 12ms，29.45%

2. 解法2：使用栈迭代的方式实现确实比较快一些，用了8ms， 77.3%。

   1. 前序遍历用栈实现也很方便，注意当前指针和stack为空的判断是或条件。代码条件比较精巧。

   ```Python
    while p is not None or len(stack) != 0:
               while p is not None:
                   result.append(p.val)
                   stack.append(p)
                   p = p.left
                   
               top = stack.pop()    
               p = top.right
   ```

   

## [145] 二叉树的后序遍历
1. 这里要注意的是，根节点要最后出栈。所以要先遍历左子树，当左子树为空时，要判断右子树是否已经访问过。所以和前序、中序遍历相比，需要一个额外的变量指示上次访问过的节点。

关于用栈迭代二叉树做个总结：三个遍历的共同点，都是先左子树、在右子树，只是在不同实际访问根节点。

1. 前序遍历：在入栈的时候即可访问当前跟节点。
2. 中序遍历：在节点出栈的时候访问跟节点
3. 后续遍历：访问左右子树后，根节点才能出栈，在出栈的时候访问节点。需要一个变量指向上次访问的节点。

递归确实是个好工具，能简化问题.



## [153] 寻找旋转排序数组中的最小值

1. 这一题折半的条件有点特殊，left 不是 mid + 1， 而是 mid，right也不是mid - 1，而是mid，为了保持左右的边界。
2. 注意，当mid不比左边大，且不比右边小的时候，说明mid和left或者right重合了。



## [155] 最小栈

1. 用栈来存储局部最小值
2. 因为出栈的时候最小值要出栈，所以当等于当前最小值的时候，也要入栈。



## [169] 多数元素

1. 解法1： 排序+计数，空间复杂度O(1)，时间复杂度 n*log(n) + n
2. 解法2：使用字典计数，空间复杂度,O(n), 最坏需要n/2空间存储位置。 时间复杂度 N
3. 解法3：Boyer-Moore 投票算法， 这个算法太漂亮了。空间负载度O(1), 时间复杂度O(N)，不可能有比这个更高效的算法了。

算法之美蕴藏在效率之中。



## [200] 岛屿数量

1. 这个题目可以近似理解为图的遍历问题，广度优先和深度优先遍历都可以。
2. 理解了题目，代码量很少。做题就很容易了。



## [206] 翻转链表

链表为空的时候要判断，一定要考虑程序的健壮性

递归版本： 关键点在于下面两句的理解，看来递归的样式很多，写出来的代码很简单，过程却有点难以理解
head.next.next = head
head.next = None

``
def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
            
        result = self.reverseList(head= head.next)
        head.next.next = head
        head.next = None
    
        return result
``

## [236] 二叉树的最近公共祖先
1. 使用递归方式实现  8m
   第一种解法
      深度优先搜索(后序遍历，先判断子节点，再判断根节点。
      如果一个节点和它的左右子树找到了两个节点， 则找到公共祖先节点
      如果在左右子树中找到一个，当前根节点满足条件，那么当前节点就是最小公共祖先节点。
   第二种解法
      原理跟上面类似，但是建立在一定有公共父节点的基础上，只要节点在树立，这个逻辑是成立的。
      p，q的公共父节点不是在root的左子树，就是在右子树，或者是root节点。参考这个[题解](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/)
   
      ```
      if root is None or root == p or root == q:
            return root
      ```

由于是深度优先搜索，所以是最近的公共祖先节点
递归思想很好用，甚至可以不需要关心具体的实现细节，只要步骤上没错就能得到答案。
运行速度也比较快，会消耗内存。

1. 非递归版本，找到p，q的父节点，再比较。  21ms， 看似操作变少了，反而更慢。



## [239] 滑动窗口最大值

1. 用双向队列来求解局部最大值。
2. 将数组的下标存入队列，而不是值，因为根据下标可以计算当前窗口大小。
3. 代码根据leetcode返回错误的数据进行调试，能求得正确结果，但是提交leetcode代码时却跑不通。有点诡异。(把成员变量替换成方法内的局部变量，看样子，是一个方法被调用了N次，但是对象只被创建了一次。)
4. 用双向队列实现的效果不高，不知道卡在哪里了。待排查。



## [367] 有效的完全平方数

1. 和69题类似，用折半查找。
2. 结束条件时left <= right, 而不是left < right，因为相等的时候可能也会是刚好要查找的值。



## [429] N叉树的层序遍历

使用队列来做层次遍历，要注意的是
1. 如何开始下一层次，每一层次出队列的次数为某一层次入队列后的长度就可以了。
2. deque 判断长度，直接 while q: 就可以判断是否为空，这个语法有点诡异啊，是否是语法糖。



## [433] 最小基因变化

跟127 单词接龙一样的，只是改了一下返回值。



## [455] 分发饼干

1. 为了简化问题，胃口大小和饼干尺寸使用前需要排序一下



## [515] 在每个树行中找最大值

在【102】层次遍历的基础上做这个题目很简单。



## [589] N叉树的前序遍历

从590拷贝代码过来，把函数名也拷贝过来了。
拷贝代码是个很容易出错的行为，要留心。



## [529] 扫雷游戏

1. 本质上还是深度优先和广度优先遍历。只是判断条件有点不同而已。



## [590] N叉树的后序遍历

迭代方式求解注意两点
1. children元素入栈的顺序从右向左
2. 判断是否pop的条件还要判断这个元素是否已经访问过，这样才不会产生死循环



## [641] 设计循环双端队列

使用front，last 都用来表示当前可以插入的位置，
front初始值为0，last初始值为1 （这个是关键）
如果获取值，front += 1， last -= 1
使用count字段来存储当前的元素个数，这样不需要浪费数组一个元素的空间来区分满和空的状态
在取模的下标计算上比较方便
浪费一个数组的空间来区别空和满的状态 



## [680] 验证回文字符串 Ⅱ

在[125]判断回文的基础上完成这个程序，这是个简单的分治。找到N和N-1的关系，比较简单。



## [703.数据流中的第-k-大元素]

1. 使用优先队列来解决这个问题，python的PriorityQueue竟然没提供类似peek的方法，而是用过pq.queue[0]来获取，这个不知道是否会影响效率。
2. 使用headqueue数据结构，效率提升了一倍。



## [860] 柠檬水找零

1. 认真读懂题目，才发现原来很简单。
2. 原来还想着用一个字典来存放5美元和10美元的计数，一个简单变量就行了，看来是牛刀用习惯了，忘记简单方法了。
3. 9月后重做的时候，20元找零，忘记判断没有10块零钱，可以找零3个5块来顶替了。



## [874] 模拟行走机器人

1. 这一题在Python的set如何支持元组的问题上有点疑义。
2. 理解起来确实比简单，知识想着有没有什么优化的方案，中间的走路的步骤一次一步是在有点慢。



## [1143] 最长公共子序列

1. 使用未缓存的递归方法，超时了。代码容易理解，但是复杂度太高。

   ```python
   def longestCommonSubsequence(self, text1: str, text2: str) -> int:
           if len(text1) == 0 or len(text2) == 0:
               return 0
           if text1[-1] == text2[-1]:
               return 1 + self.longestCommonSubsequence(text1[0:-1], text2[0: -1])
           else:
               return max(self.longestCommonSubsequence(text1, text2[0:-1]),  self.longestCommonSubsequence(text1[0:-1], text2))
   ```

   > ```
   > "ylqpejqbalahwr"
   > "yrkzavgdmdgtqpg"
   > 在这个测试用例的时候超时了
   > ```

2. 使用带缓存的递归方法：

   ```Python
   def longestCommonSubsequence(self, text1: str, text2: str) -> int:
           return self.longestCommonSubsequenceWithCache(text1, text2, {})
   
       def longestCommonSubsequenceWithCache(self, text1: str, text2: str, cache: dict) -> int:
           if len(text1) == 0 or len(text2) == 0:
               return 0
           if text1[-1] == text2[-1]:
               key = text1[0:-1] + " " + text2[0:-1]
               if key in cache:
                   return 1 + cache[key]
               else:
                   value = self.longestCommonSubsequenceWithCache(text1[0:-1], text2[0: -1], cache)
                   cache[key] = value
                   return value + 1
           else:
               key1 = text1 + " " + text2[0:-1]
               value1 = 0
               if key1 in cache:
                   value1 = cache[key1]
               else:
                   value1 = self.longestCommonSubsequenceWithCache(text1, text2[0:-1], cache)
                   cache[key1] = value1
               
               key2 = text1[0:-1] + " " + text2
               value2 = 0
               if key2 in cache:
                   value2 = cache[key2]
               else:
                   value2 = self.longestCommonSubsequenceWithCache(text1[0:-1], text2, cache)
                   cache[key2] = value2
               return max(value1, value2)
   ```

   

   >```
   >在使用下面这个用例的时候超时了。
   >"fcvafurqjylclorwfoladwfqzkbebslwnmpmlkbezkxoncvwhstwzwpqxqtyxozkpgtgtsjobujezgrkvevklmludgtyrmjaxyputqbyxqvupojutsjwlwluzsbmvyxifqtglwvcnkfsfglwjwrmtyxmdgjifyjwrsnenuvsdedsbqdovwzsdghclcdexmtsbexwrszihcpibwpidixmpmxshwzmjgtadmtkxqfkrsdqjcrmxkbkfoncrcvoxuvcdytajgfwrcxivixanuzerebuzklyhezevonqdsrkzetsrgfgxibqpmfuxcrinetyzkvudghgrytsvwzkjulmhanankxqfihenuhmfsfkfepibkjmzybmlkzozmluvybyzsleludsxkpinizoraxonmhwtkfkhudizepyzijafqlepcbihofepmjqtgrsxorunshgpazovuhktatmlcfklafivivefyfubunszyvarcrkpsnglkduzaxqrerkvcnmrurkhkpargvcxefovwtapedaluhclmzynebczodwropwdenqxmrutuhehadyfspcpuxyzodifqdqzgbwhodcjonypyjwbwxepcpujerkrelunstebopkncdazexsbezmhynizsvarafwfmnclerafejgnizcbsrcvcnwrolofyzulcxaxqjqzunedidulspslebifinqrchyvapkzmzwbwjgbyrqhqpolwjijmzyduzerqnadapudmrazmzadstozytonuzarizszubkzkhenaxivytmjqjgvgzwpgxefatetoncjgjsdilmvgtgpgbibexwnexstipkjylalqnupexytkradwxmlmhsnmzuxcdkfkxyfgrmfqtajatgjctenqhkvyrgvapctqtyrufcdobibizihuhsrsterozotytubefutaxcjarknynetipehoduxyjstufwvkvwvwnuletybmrczgtmxctuny"
   >"nohgdazargvalupetizezqpklktojqtqdivcpsfgjopaxwbkvujilqbclehulatshehmjqhyfkpcfwxovajkvankjkvevgdovazmbgtqfwvejczsnmbchkdibstklkxarwjqbqxwvixavkhylqvghqpifijohudenozotejoxavkfkzcdqnoxydynavwdylwhatslyrwlejwdwrmpevmtwpahatwlaxmjmdgrebmfyngdcbmbgjcvqpcbadujkxaxujudmbejcrevuvcdobolcbstifedcvmngnqhudixgzktcdqngxmruhcxqxypwhahobudelivgvynefkjqdyvalmvudcdivmhghqrelurodwdsvuzmjixgdexonwjczghalsjopixsrwjixuzmjgxydqnipelgrivkzkxgjchibgnqbknstspujwdydszohqjsfuzstyjgnwhsrebmlwzkzijgnmnczmrehspihspyfedabotwvwxwpspypctizyhcxypqzctwlspszonsrmnyvmhsvqtkbyhmhwjmvazaviruzqxmbczaxmtqjexmdudypovkjklynktahupanujylylgrajozobsbwpwtohkfsxeverqxylwdwtojoxydepybavwhgdehafurqtcxqhuhkdwxkdojipolctcvcrsvczcxedglgrejerqdgrsvsxgjodajatsnixutihwpivihadqdotsvyrkxehodybapwlsjexixgponcxifijchejoxgxebmbclczqvkfuzgxsbshqvgfcraxytaxeviryhexmvqjybizivyjanwxmpojgxgbyhcruvqpafwjslkbohqlknkdqjixsfsdurgbsvclmrcrcnulinqvcdqhcvwdaxgvafwravunurqvizqtozuxinytafopmhchmxsxgfanetmdcjalmrolejidylkjktunqhkxchyjmpkvsfgnybsjedmzkrkhwryzan"
   >```

3. 使用@lru_cache() 可以达到和2一样的效果。

   ```python
   @lru_cache()
       def longestCommonSubsequence(self, text1: str, text2: str) -> int:
           if len(text1) == 0 or len(text2) == 0:
               return 0
           if text1[-1] == text2[-1]:
               return 1 + self.longestCommonSubsequence(text1[0:-1], text2[0: -1])
           else:
               return max(self.longestCommonSubsequence(text1, text2[0:-1]),  self.longestCommonSubsequence(text1[0:-1], text2))
            
   ```

4. 使用递推迭代的方法，代码简单，却有又不少机关

   1. dp = [[0] * (n + 1) for _ in range(m + 1)] 创建二维数组
   2. 三目运算
   3. **递推公式**

   ```python
   def longestCommonSubsequence(self, text1: str, text2: str) -> int:
           m = len(text1)
           n = len(text2)
           dp = [[0] * (n + 1) for _ in range(m + 1)]
           for i, c in enumerate(text1):
               for j, d in enumerate(text2):              
                   dp[i+1][j+1] = dp[i][j] + 1 if c == d else max(dp[i][j+1], dp[i+1][j])
           return dp[-1][-1]
   ```

5. 动态规划，状态之间的关系

   ```swift
   if firstCharacters[i - 1] == secondCharacters[j - 1] {
      dp[i][j] = dp[i-1][j-1] + 1
   }else{
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   }
   ```