1143. 最长公共子序列


1143. 最长公共子序列

一个字符串的   子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,”ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
参考:https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-tu-wen-jie-xi-by-yijiaoqian/

     public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) &#123;
            for (int j = 0; j < n; j++) &#123;
                // 获取两个串字符
                char c1 = text1.charAt(i), c2 = text2.charAt(j);
                if (c1 == c2) &#123;
                    // 去找它们前面各退一格的值加1即可
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                &#125; else &#123;
                    //要么是text1往前退一格,要么是text2往前退一格,两个的最大值
                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                &#125;
            &#125;
        &#125;
        return dp[m][n];
    &#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 52. 两个链表的第一个公共节点 剑指 Offer 52. 两个链表的第一个公共节点
剑指 Offer 52. 两个链表的第一个公共节点 public ListNode getIntersectionNode(ListNode headA, ListNode headB) &#123; List
2021-02-25 future
下一篇 
7. 整数反转 7. 整数反转
7. 整数反转 考虑溢出class Solution &#123; public int reverse(int x) &#123; int ans = 0; while (x !=
2021-02-24 future
  目录