题解 | #最长公共前缀#

import java.lang.String;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    /******************************************************************************************************/
    // 以下方法为前缀树实现最长公共前缀(注意:有个天坑！！！就是字符串长度以及字符串的数量不能太多，否则就会报错 Exception in thread "main" java.lang.OutOfMemoryError: Java heap space)
    // 这种方法在数据量小的时候挺好用的！！！但是，数据量大，就有问题了！！！
    /*
    // 定义一个内部类，这个类是一个节点(前缀树)
    class PreNode {
        // 属性
        int pre; // 有多少个字符串经过这个节点
        int end; // 有多少个字符串以该节点为结尾
        PreNode[] ps = new PreNode[26]; // 存放路径，小写英文字母 a~z
        // 构造器
        PreNode(int pre, int end) {
            this.pre = pre;
            this.end = end;
        }
    }
    
    public String longestCommonPrefix (String[] strs) {
        // write code here
        if (0 == strs.length) {
            return "";
        }
        if (1 == strs.length) {
            return strs[0];
        }
        // 具体代码实现
        PreNode rt = new PreNode(0, 0);
        // 定义一个辅助节点
        PreNode tn = rt;
        // 定义一个index索引
        int index = 0;
        // 整个数组中，最长的字符串
        String ms = "";
        // 前缀树
        for (String str : strs) { // 从数组中获取一个字符串
            ms = str.length() > ms.length() ? str : ms; // 获取整个数组中最长的字符串
            tn.pre++; // 根节点的 pre 值，说明了到底添加了多少个字符串
            char[] chs = str.toCharArray(); // 将字符串转换为字符数组
            for (char ch : chs) { // 遍历字符数组
                index = ch - 'a'; // 计算 index 索引
                if (null == tn.ps[index]) {
                    // 如果为空，那么我们就为它新建一条路径
                    PreNode nn = new PreNode(1, 0); // 新建一个节点
                    tn.ps[index] = nn; // 建立连接
                    tn = nn;
                }
                else {
                    // 如果不为空，我们直接移动到这个节点上
                    tn = tn.ps[index];
                    tn.pre++;
                }
            }
            // 此时在最后一个节点上
            tn.end++;
            // 重新初始化
            tn = rt;
        }
        // 循环结束后，我们成功构造出了一棵前缀树。同时，我们得到了整个数组中最长的字符串
        // 定义一个切片索引
        int si = -1;
        // 将字符串转换为字符数组
        for (char ch : ms.toCharArray()) {
            index = ch - 'a'; // 计算 index 索引
            if (tn.ps[index].pre == rt.pre) {
                si++;
                tn = tn.ps[index];
            }
            else {
                break;
            }
        }
        return ms.substring(0, si + 1);
    }
    */
    
    public String longestCommonPrefix (String[] strs) {
        // write code here
        if (0 == strs.length) {
            return "";
        }
        if (1 == strs.length) {
            return strs[0];
        }
        // 具体代码实现
        // 初始化
        String ss = strs[0];
        // 定义一个切割索引
        int index = Integer.MAX_VALUE;
        // 定义一个指针
        int p = 0;
        // 定义一个临时变量
        String tmp = "";
        // 定义一个长度
        int ml = 0;
        for (int i = 1; i < strs.length; i++) {
            tmp = strs[i]; // 获取一个字符串
            ml = ss.length() >= tmp.length() ? tmp.length() : ss.length();
            while (p < ml) {
                if (ss.charAt(p) == tmp.charAt(p)) {
                    p++;
                }
                else {
                    break;
                }
            }
            index = Math.min(p - 1, index);
            p = 0;
            ss = ss.length() >= tmp.length() ? tmp : ss;
        }
        return ss.substring(0, index + 1);
    }
}