java最长公共前缀算法实现_判断字符串在前缀树最大前缀

1.知识点总结

代码如下

while(index<length&&str1.charAt(index)==str2.charAt(index)) {//如果两个字符串中索引所对应的值是相同的，则索引值加1，继续比较后面的
           index++;
        }
1
2
3

Java中的charAt()方法可返回指定位置的字符。如str，s就为索引为0的位置的字符

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            System.out.println("请输入字符串：");
            String str = sc.nextLine().toString();//可以读取一整行，包括了空格，next()却不能读入
            String arr[] = str.split(" ");//拆分字符串成字符串数组
            System.out.println("最长公共前缀:" + one.longest(arr));
        }
    }

1
2
3
4
5
6
7
8
9
10

这里我们首先进行输入字符串，然后用split将输入的字符串转变为字符数组，如首先输入abc再空格输入cde.此时abc与cde便就成了数组中的两个元素

2.全部代码

import java.util.Scanner;
public class one {
    //最长公共前缀
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            System.out.println("请输入字符串：");
            String str = sc.nextLine().toString();//可以读取一整行，包括了空格，next()却不能读入
            String arr[] = str.split(" ");//拆分字符串成字符串数组
            System.out.println("最长公共前缀:" + one.longest(arr));
        }
    }
    public static String longest(String[] strs) {
        if (strs == null || strs.length == 0) { // 如果是空串则直接空格；
            return "没有前缀";
        }
        String prefix = strs[0]; //prefix用来保存公共前缀
        int count = strs.length;  //字符串长度
        for (int i = 0; i < count; i++) {
            prefix = longest(prefix, strs[i]);//循环遍历字符数组寻取最长公共前缀
            if (prefix.length() == 0) {//如果没有公共前缀则直接退出
                break;
            }
        }
        return prefix;//返回公共前缀的值
    }

    public static String longest(String str1, String str2) {
        int length=Math.min(str1.length(),str2.length());//长度为字符串最短的
        int index=0;//字符串的索引值
        while(index<length&&str1.charAt(index)==str2.charAt(index)) {//如果两个字符串中索引所对应的值是相同的，则索引值加1，继续比较后面的
           index++;
        }
        return str1.substring(0,index);//截取两个字符串中前index+1相同的元素并将其返回
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37