Longest Common Prefix, Leetcode 解题笔记

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

这道题思路很简单,就是从每个String的第一个字符开始比较,如果都相同,比第二个,以此类推。结束条件为两个中的任意一个:
1. strings某一位的字符不一致
2. 比较途中最短的string到尽头了

虽然思路简单,但是实现中有很多陷阱,比如对空数组,空字符串的处理。所以要想在面试中考虑到所有的test case还是很难的。
下面的code我修改了三次才成功通过,主要是轻敌了,没有把所有情况想清楚。

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int prefix = 0;
        boolean keepgoing = true;
        if(strs.length == 0) return new String("");
        if(strs.length == 1) return strs[0];
        if(strs[0].length() == 0) return new String("");
        while(keepgoing){
            for(int i = 1; i < strs.length; i++){
                if(strs[i].length() == 0) return new String("");
                if(prefix >= strs[i].length() || prefix >= strs[0].length()){
                    keepgoing = false;
                    break;
                }
                char pre = strs[i-1].charAt(prefix);
                char cur = strs[i].charAt(prefix);
                if(pre != cur){
                    keepgoing = false;
                    break;
                }
            }
            if(keepgoing){
                prefix++;
            }
        }
        return strs[0].substring(0,prefix);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s