找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6435|回复: 12
收起左侧

[米群网刷题小分队] [LeetCode] String 题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-11-2014 11:10 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 MengMa 于 12-12-2014 08:36 PM 编辑

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. }
复制代码


本帖被以下淘专辑推荐:

发表于 12-11-2014 11:27 PM | 显示全部楼层
bruteforce

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-11-2014 11:35 PM | 显示全部楼层

有啥优化解法吗。。。这个BF解法我还理解了好久。智商是硬伤。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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