找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2238|回复: 8
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Longest Common Prefix】-【刷题第一弹】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-23-2014 06:16 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:47 AM 编辑

快速通道:
https://oj.leetcode.com/problems/longest-common-prefix/


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================

思路:目前给的是O(n^2)的实现,

java代码:
  1. public String longestCommonPrefix(String[] strs) {
  2.         if(strs==null||strs.length==0)  return "";
  3.         if(strs.length==1)  return strs[0];
  4.         String first=strs[0];
  5.         int len=0;
  6.         for(int i=0;i<first.length();++i){
  7.             char c=first.charAt(i);
  8.             int j=1;
  9.             for(;j<strs.length;++j){
  10.                 if(i>=strs[j].length()||strs[j].charAt(i)!=c)    break;
  11.             }
  12.             if(j!=strs.length)
  13.                 return first.substring(0,len);
  14.             len++;
  15.         }
  16.         return first.substring(0,len);
  17.     }
复制代码


复杂度:O(n^2)

本帖被以下淘专辑推荐:

18

主题

9

精华

522

积分

超级会员

Rank: 4

积分
522
发表于 11-17-2014 03:27 PM | 显示全部楼层
参考别人的一个更简洁的解法,复杂度还是O(n^2)
  1. class Solution {
  2. public:
  3.     string longestCommonPrefix(vector<string> &strs) {
  4.         if(strs.empty()) return "";
  5.         
  6.         for(int i = 0; i < strs.front().size(); ++i){
  7.             for(int j = 1; j < strs.size(); ++j){
  8.                 if(strs[0][i] != strs[j][i]) return strs[0].substr(0, i);
  9.             }
  10.         }
  11.         
  12.         return strs[0];
  13.     }
  14. };
复制代码
回复 支持 1 反对 0

使用道具 举报

2

主题

1

精华

133

积分

资深会员

Rank: 2

积分
133
发表于 11-17-2014 07:47 PM | 显示全部楼层
思路:最长共用前缀一定小于等于容器中长度最小的字串,且小于等于任何两字串的共用前缀,那么先找到最小字符串的长度,再逐一比较,每当找到更短的共用前缀,就缩短查找范围

  1. <div>string longestCommonPrefix(vector<string> &strs) </div><div>{</div><div>        if (strs.empty())</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>{</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return "";</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div>
  2. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>int end = <span style="line-height: 1.5;">strs.at(0).size();</span></div><div>
  3. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>for (int i = 0; i < strs.size(); i++)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>{</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>end = min(end, (int)strs.at(i).size());</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div>
  4. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>for (int i = 1; i < strs.size(); i++)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>{</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>for (int j = 0; j < end; j++)</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>{</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>if (strs.at(0).at(j) != strs.at(i).at(j))</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>{</div><div><span class="Apple-tab-span" style="white-space:pre">                                </span>end = j;</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div>
  5. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return strs.at(0).substr(0, end);</div><div>}</div>
复制代码
复杂度
时间:一般情况,O(n * m) , m为min(任意两个字符串的common prefix中的最长者, 最短字串的长度)
          最坏情况,m = n,即O(n^2)
注:假定string::size()和vector::size()函数是O(1)复杂度
空间: O(1)

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表