【LeetCode】Longest Common Prefix

谁借莪１个温暖的怀抱￠ 2021-12-13 23:25 127阅读 0赞

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

java code : 预处理出最短串与任意一字符串的公共前缀，用StringBuilder保存，再去遍历剩余字符串，从尾处开始推。

复杂度O(m \* n)  m : length of the arrays, n ：length of the prefix

public class Solution {
        public String longestCommonPrefix(String[] strs) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
             int numofstr = strs.length;
    		 if(numofstr < 1)
    			 return new String("");
    		 if(numofstr == 1)
    			 return strs[0];
    		 StringBuilder res = new StringBuilder();
    		 String minlen = strs[0];
    		 int indexmin = 0;
    		 for(int i = 1; i < numofstr; i++)
    		 {
    			 if(minlen.length() > strs[i].length())
    			 { minlen = strs[i];indexmin = i;}
    		 }
    		 String str1 = strs[0];
    		 String str2 = strs[1];
    		 int index2 = 1;
    		 if(minlen.equals(strs[0]))
    		 {
    			 str1 = minlen;
    			 str2 = strs[1];
    		 }
    		 else
    		 {
    			 str1 = minlen;
    			 str2 = strs[0];
    			 index2 = 0;
    		 }
    		 int i = 0, j = 0;
    		 while(i < str1.length() && j < str2.length())
    		 {
    			 if(str1.charAt(i) == str2.charAt(j))
    			 {
    				 res.append(str1.charAt(i));
    				 i++;j++;
    				 continue;
    			 }
    			 break;
    		 }
    		 if(numofstr < 3 || res.length() == 0)
    			 return res.toString();
    		 for(int k = 0; k < numofstr; k++)
    		 {
    			 if(k == indexmin || k == index2)
    				 continue;
    			 int len = res.length();
    			 String cur = strs[k];
    			 while(len > 0 && (cur.charAt(len - 1) != res.charAt(len - 1)))
    			 {
    				 res.deleteCharAt(len - 1);
    				 len--;
    			 }
    			 
    		 }
    		 return res.toString();
            
        }
    }

转载于:https://www.cnblogs.com/james1207/p/3395514.html