我是图片

leetcode14 : 最长公共前缀


摘要: 分享一些leetcode

题目:

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例:

输入: ["flower","flow","flight"]
输出: "fl"

地址:https://leetcode-cn.com/problems/longest-common-prefix/

public static String longestCommonPrefix(String[] strs) {
            if(strs.length == 0)
                return "";
            String ans = strs[0];
            for(int i =1;i<strs.length;i++) {
                int j=0;
                for(;j<ans.length() && j < strs[i].length();j++) {
                    if(ans.charAt(j) != strs[i].charAt(j))
                        break;
                }
                ans = ans.substring(0, j);
                if(ans.equals(""))
                    return ans;
            }
            return ans;
        }

执行用时:3 ms, 在所有 Java 提交中击败了21.65%的用户

内存消耗:37.9 MB, 在所有 Java 提交中击败了40.65%的用户

上面的解法是从题解中找来的,我的第一种思路也是如此,一个横向的遍历。

但是如果纵向扫描会更快

if (strs == null || strs.length == 0) {
                return "";
            }
            int length = strs[0].length();
            int count = strs.length;
            for (int i = 0; i < length; i++) {
                char c = strs[0].charAt(i);
                for (int j = 1; j < count; j++) {
                    if (i == strs[j].length() || strs[j].charAt(i) != c) {
                        return strs[0].substring(0, i);
                    }
                }
            }
            return strs[0];

执行用时:1 ms, 在所有 Java 提交中击败了84.63%的用户

内存消耗:37.6 MB, 在所有 Java 提交中击败了83.35%的用户

点赞
32
赞赏


  • 作者:kuls
  • 简介:一个热爱编程的小伙子!
  • 版权:转载文章需找站长授权,未经授权转载,必会追究!
二维码

评论

留言