No.014：Longest Common Prefix

问题：

Write a function to find the longest common prefix string amongst an array of strings.

官方难度：

Easy

翻译：

寻找一个字符串数组的最长公共前缀。

方法一：

数组长度为0，返回空字符串。
将数组第一项，作为初始的公共前缀。
从数组第二项开始进入循换，整理当前字符和当前前缀字符的长度。
以小长度的字符串为基准，从头开始逐个匹配，遇到不同的字符时，更新前缀字符。
为防止完全匹配情况，如“aa”匹配“aaa”。由于不存在不同的字符，所以不会更新的情况，设定更新标志位flag，当flag为false时，将前缀字符更新为小长度字符。
在内循环结束之后，若得到的前缀字符长度为0，直接跳出整个循环。
外循环可以使用foreach循环。

方法一的解题代码：

     private static String method(String[] strs) {

         String prefix = strs.length == 0 ? "" : strs[0];

         // 从数组第二项开始遍历

         for (String compare : strs) {

             // 整理长度

             String s1 = prefix.length() > compare.length() ? compare : prefix;

             String s2 = prefix.length() > compare.length() ? prefix : compare;

             boolean flag = false;

             for (int j = 0; j < s1.length(); j++) {

                 if (s1.charAt(j) != s2.charAt(j)) {

                     prefix = prefix.substring(0, j);

                     flag = true;

                     break;

                 }

             }

             // 防止完全匹配的情况

             if (!flag) {

                 prefix = s1;

             }

             if (prefix.length() == 0) {

                 break;

             }

         }

         return prefix;

     }

method

方法二：

其实，String类自带了String.startWith()的实例方法，来判断一个字符串是否以另一个字符串为开头的形式。使用这种方法可以进一步地增强效率。
在内循环中，判断当前字符是否匹配当前前缀，若不是消去前缀字符串的最后一个字符，直到匹配成功。
注意入参检查。

方法二的解题代码：

     public static String longestCommonPrefix(String[] strs) {

         if (strs == null) {

             throw new IllegalArgumentException("Input error");

         }

         String prefix = strs.length == 0 ? "" : strs[0];

         for (String compare : strs) {

             while (!compare.startsWith(prefix)) {

                 // 不匹配，消去前缀最后一项

                 prefix = prefix.substring(0, prefix.length() - 1);

             }

             if (prefix.length() == 0) {

                 break;

             }

         }

         return prefix;

     }

longestCommonPrefix

巴特西

No.014：Longest Common Prefix

最新文章

热门文章