Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.
(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)
Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties.Note:
1 <= str1.length, str2.length <= 1000 str1 and str2 consist of lowercase English letters.
思路
先用 dp 求出 lms,因为题目要求结果串包含 s1 和 s2 的所有字符,而 lms 中可能包含不全,所以我们还要将没有出现在 lms 中的字符拼接到 ans 中…
class Solution { String LMS(char[] s1, char[] s2, int n, int m) { String f[][] = new String[n+1][m+1]; for (int i = 0; i <= n; i++) Arrays.fill(f[i], ""); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (s1[i-1] == s2[j-1]) f[i][j] = f[i-1][j-1] + s1[i-1]; else f[i][j] = f[i-1][j].length() > f[i][j-1].length() ? f[i-1][j] : f[i][j-1]; } return f[n][m]; } public String shortestCommonSupersequence(String str1, String str2) { char[] s1 = str1.toCharArray(), s2 = str2.toCharArray(); int n = s1.length, m = s2.length; String lms = LMS(s1, s2, n, m); StringBuilder ans = new StringBuilder(); int i = 0, j = 0; for (char c : lms.toCharArray()) { while (i < n && s1[i] != c) ans.append(s1[i++]); while (j < m && s2[j] != c) ans.append(s2[j++]); ans.append(c); i++; j++; } ans.append(str1.substring(i)); ans.append(str2.substring(j)); return ans.toString(); } }dp 求 lms 那里频繁的字符串拼接是整个算法的瓶颈,所以可优化的地方在这