[LeetCode] String 题目

MengMa

Longest Common Prefix


思路：http://codeganker.blogspot.com/search?q=common

具体来说：

选择第一个字符串做标准，然后逐一扫描字符串数组的在特定位置cur的字符。（cur表示待比较的位置，且cur的数值为当前的最长substring）
如果全部其他字符串在位置cur的字符都和标准字符串相同，则cur ++
并把那个字符加入到结果中。

时间 O (mn) , m为字符串最大长度，n为字符串数组内的元素个数。空间为O（m）

代码

1. public class Solution {
   
2.     public String longestCommonPrefix(String[] strs) {
   
3.         StringBuilder res = new StringBuilder();
   
4.         if(strs == null || strs.length == 0) return res.toString();
   
5.         boolean isSame = true;
   
6.         int cur = 0;// indicates how many chars have been validated in the standard
   
7.         while(isSame)
   
8.         {
   
9.             for(int i = 0; i < strs.length; i++)
   
10.             {
    
11.                 if(strs【i】.length() <= cur || strs【i】.charAt(cur) != strs[0].charAt(cur))
    
12.                 {
    
13.                     isSame = false;
    
14.                     break;
    
15.                 }
    
16.             }
    
17.             if(isSame)
    
18.                 res.append(strs[0].charAt(cur));
    
19.             cur ++;
    
20.         }
    
21.         return res.toString();
    
22.     }
    
23. }

复制代码

cpcs

bruteforce

MengMa

cpcs 发表于 12-11-2014 11:27 PM
bruteforce

有啥优化解法吗。。。这个BF解法我还理解了好久。智商是硬伤。