给出两个字符串,找到最长公共子串,并返回其长度。 注意事项 子串的字符应该连续的出现在原字符串中,这与子序列有所不同。给出两个字符串,找到最长公共子串,并返回其长度

原创
2017/06/13 23:57
阅读数 78

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        if(A.length()==0 || null==A || B.length()==0 || null==B) return 0;
        List<Integer> list = new ArrayList<Integer>();
        List<String> alist = new ArrayList<String>();
        List<String> blist = new ArrayList<String>();
        alist.addAll(text(A));
        blist.addAll(text(B));
        for(int i=0;i<alist.size();i++){
            for(int j=0;j<blist.size();j++) {
                if(alist.get(i).equals(blist.get(j))) {
                    list.add(alist.get(i).length());
                }
            }
        }
        Collections.sort(list);
        return list.get(list.size()-1);
    }
    
    public Set<String> text(String s) {
        Set<String> set = new HashSet<String>();
        for(int i=0;i<s.length();i++) {
            for(int j = s.length();j>0;j--){
                if(i<j) {
                    set.add(s.substring(i,j));
                }
            }
        }
        return set;
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部