Longest Common Prefix 解答

Question

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

Solution

第一思路是用Trie，但是对于一道Easy类别的题目，用Trie显然是杀鸡用牛刀。

于是我们可以参考到构造Trie的过程，来找这个最长prefix。

我们先用String array中第一个String初始化Pre，然后遍历剩下的每一个String，找重合的终点，删除不重合的部分。

 public class Solution {

     public String longestCommonPrefix(String[] strs) {

         if (strs == null || strs.length < 1) {

             return "";

         }

         int length = strs.length;

         int initLen = strs[0].length();

         StringBuilder result = new StringBuilder(initLen);

         for (int i = 0; i < initLen; i++) {

             result.append(strs[0].charAt(i));

         }

         for (int i = 1; i < length; i++) {

             String curString = strs[i];

             initLen = result.length();

             for (int j = 0; j < initLen; j++) {

                 if (j < curString.length() && curString.charAt(j) == result.charAt(j)) {

                     continue;

                 }

                 result.delete(j, initLen);

                 break;

             }

         }

         return result.toString();

     }

 }

更简单的方法是用String.indexOf()的方法来判断重合终点。

 public class Solution {

     public String longestCommonPrefix(String[] strs) {

         if (strs == null || strs.length < 1) {

             return "";

         }

         int length = strs.length;

         int initLen = strs[0].length();

         String prev = strs[0];

         for (int i = 0; i < length; i++) {

             String curString = strs[i];

             while (curString.indexOf(prev) != 0) {

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

             }

         }

         return prev;

     }

 }

巴特西

Longest Common Prefix 解答

Question

Solution

最新文章

热门文章