首页 > 其他 > 详细

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.

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)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!