文档章节

给k个字符串,求出他们的最长公共前缀(LCP)

 小杰kkk
发布于 2017/06/14 02:09
字数 222
阅读 12
收藏 0

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public String longestCommonPrefix(String[] strs) {
        // write your code here
        if(strs.length == 0 || strs == null) return "";
        Map<String,Integer> map = new HashMap<String,Integer>();
        List<String> list = new ArrayList<String>();
        for(int i=0;i<strs.length;i++){
            List<String> alist = new ArrayList<String>();
            if(strs[i] == null || strs[i].equals("")) return "";
            alist.addAll(text(strs[i]));
            for(int j=0;j<alist.size();j++) {
                String b = alist.get(j);
                if(!map.containsKey(b)) {
                    map.put(b, 1);
                } else {
                    int id=map.get(b);
                    id++;
                    map.put(b, id);
                }
            }
        }
        Set<String> sss = map.keySet();
        list.addAll(sss);
        List<String> alist = new ArrayList<String>();
        for(int i=0;i<list.size();i++){
            if(map.containsKey(list.get(i)) && map.get(list.get(i))==strs.length) {
                alist.add(list.get(i));
            }
        }
        int flag=0;
        for(int i=0;i<alist.size() && flag==0;i++) {
            flag=1;
            for(int j=i+1;j<alist.size();j++) {
                int a = alist.get(i).length();
                int b = alist.get(j).length();
                if (a>b) {
                    flag=0;
                    String c = alist.get(i);
                    alist.set(i, alist.get(j));
                    alist.set(j, c);
                }
            }
        }
        return alist.get(alist.size()-1);
    }
    
    public Set<String> text(String s) {
        Set<String> set = new HashSet<String>();
        for(int i=s.length();i>0;i--) {
            set.add(s.substring(0,i));
        }
        return set;
    }
}

© 著作权归作者所有

粉丝 0
博文 6
码字总数 976
作品 0
宿州
私信 提问
manacher&&后缀数组

一、manacher: 1、主体思想: 用一个辅助数组P记录以每个字符为中心的最长回文半径。 P[i]最小为1, 此时回文串为Str[i] 本身。 MaxId:之前所有求出的回文串所能到达的最右端点 id:能到达...

luodanyu_
2017/12/22
0
0
【XSY2715】回文串 树链剖分 回文自动机

题目描述   有一个字符串 ,长度为 。有 个操作:   求    题解   毒瘤题。   先把所有操作保存下来,求出最终的字符串。   观察到操作过程中每个字符串都只会出现一次,而且左边...

ez_yww
2018/01/11
0
0
字符串专题讲解

最近教练叫我去讲字符串专题,于是来写一写这方面的内容 主要就讲以下几个吧: 1.Kmp 2.Extended Kmp 3.Trie 4*.AC Automation (Trie Graph) 5*.String Hash 6.Suffix Array 7*.Suffix Auto...

JacaJava
2017/11/26
0
0
NOIP2017提高组 模拟赛 27(总结)

NOIP2017提高组 模拟赛 27(总结) 第一题 回文数 (推公式+快速幂) 【题目描述】 【解题思路】   长度为1的字符串,s[1]=9。   长度为3的字符串,s[3]=10*9。   长度为5的字符串,s...

kekxy
2017/10/21
0
0
CS Academy Round #49 C.Max Substring 【后缀数组】

MaxSubstring Time limit: 1000 ms Memory limit: 256 MB You are given a string S.Find a string T thathas the most number of occurrences as a substring in S. If the solution is not......

my_sunshine26
2017/09/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 年迈渔夫遭黑帮袭抢

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享Elvis Presley的单曲《White Christmas》: 《White Christmas》- Elvis Presley 手机党少年们想听歌,请使劲...

小小编辑
今天
1K
20
CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
16
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部