高频面试题之最长公共系列

高频面试题总结 —— 最长公共系列

最长公共子串

给出两个字符串，找到最长公共子串，并返回其长度。

样例:
给出A=“ABCD”，B=“CBCE”，返回 2

思路：

动态规划求解：

• 当A.charAt(i) == B.charAt(j), 状态转移：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = 0
• 最后求max(dp)

代码：

public class Solution {
    /*
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        int lenA = A.length();
        int lenB = B.length();
        
        int[][] dp = new int[lenA + 1][lenB + 1];
        
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        int max = 0;
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                max = Math.max(dp[i][j], max);
            }
        }
        
        return max;
    }
}

最长公共子序列

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

样例:
给出”ABCD” 和 “EDCA”，这个LCS是 “A” (或 D或C)，返回1
给出 “ABCD” 和 “EACB”，这个LCS是”AC”返回 2

public class Solution {
    /*
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        
        int lenA = A.length();
        int lenB = B.length();
        int[][] dp = new int[lenA + 1][lenB + 1];
        
        if (lenA == 0 || lenB == 0 || A == null || B == null)
            return 0;
        
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1))
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        return dp[lenA][lenB];
    }
}

网易面试题

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

样例：
输入:
x.nowcoder.com
ooo
输出:
Yes

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String t = scan.nextLine();
        int lenS = s.length();
        int lenT = t.length();
        
        int[][] dp = new int[lenS+1][lenT+1];
        
        if (lenT == 0 || lenS == 0 || s == null || t == null) {
            System.out.println("No");
            return;
        }
        
        for (int i = 1; i <= lenS; i++) {
            for (int j = 1; j <= lenT; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        if (dp[lenS][lenT] == lenT) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}