Longest Common Subsequence & Substring & prefix

时间：2016-07-06 13:13:35 阅读：132 评论：0 收藏：0 [点我收藏+]

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

分析：

典型的DP。

 1 public class Solution {
 2     /**
 3      * @param A, B: Two strings.
 4      * @return: The length of longest common subsequence of A and B.
 5      */
 6     public int longestCommonSubsequence(String str1, String str2) {
 7         if (str1 == null || str2 == null) return 0;
 8         int[][] opt = new int[str2.length() + 1][str1.length() + 1];
 9         
10         for (int j = 0; j <= str1.length(); j++) {
11             for (int i = 0; i <= str2.length(); i++) {
12                 if (i == 0 || j == 0) {
13                     opt[i][j] = 0;
14                 } else if (str2.charAt(i-1) == str1.charAt(j-1)) {
15                     opt[i][j] = opt[i-1][j-1] + 1;
16                 } else {
17                     opt[i][j] = Math.max(opt[i-1][j], opt[i][j-1]);
18                 }
19             }
20         }
21         return opt[str2.length()][str1.length()];
22     }
23 }

Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Notice

The characters in substring should occur continuously in original string. This is different with subsequence.

Example

Given A = "ABCD", B = "CBCE", return 2.

分析：

从头比到尾呗。

 1 public class Solution {
 2     /**
 3      * @param A, B: Two string.
 4      * @return: the length of the longest common substring.
 5      */
 6     public int longestCommonSubstring(String A, String B) {
 7         if (A == null || B == null || A.length() == 0 || B.length() == 0) return 0;
 8         int max = 0;
 9         for (int i = 0; i < B.length(); i++) {
10             for (int j = 0; j < A.length(); j++) {
11                 int incr = 0;
12                 while (i + incr < B.length() && j + incr < A.length() && (B.charAt(i + incr) == A.charAt(j + incr))) {
13                     incr++;
14                     max = Math.max(max, incr);
15                 }
16             }
17         }
18         return max;
19     }
20 }

Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"

分析：

取出第一个string和剩余的string相比即可。

 1 public class Solution {
 2     /**
 3      * @param strs: A list of strings
 4      * @return: The longest common prefix
 5      */
 6     public String longestCommonPrefix(String[] strs) {
 7         if (strs == null || strs.length == 0) return "";
 8         if (strs.length == 1) return strs[0];
 9         
10         StringBuilder sb = new StringBuilder();
11 
12         for (int j = 0; j < strs[0].length(); j++) {
13             for (int i = 1; i < strs.length; i++) {
14                 if (j >= strs[i].length() || strs[i].charAt(j) != strs[0].charAt(j)) {
15                     return sb.toString();
16                 }
17             }
18             sb.append(strs[0].charAt(j));
19         }
20         return sb.toString();
21     }
22 }

Longest Common Subsequence & Substring & prefix

原文：http://www.cnblogs.com/beiyeqingteng/p/5646533.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)