LeetCode 14.最长公共前缀

2019-05-04  本文已影响0人  饼干不干

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

思路分析

取第一个单词的index位置字符,然后遍历其它所有单词该位置是否为该字符,不是则结束,是则继续下一个位置。注意输入可能为空

C

    if(strsSize==0)
        return "";
    int index=0,i=0;
    char flag=strs[0][index];
    while(flag){
        for(i=1;i<strsSize;i++){
            if(strs[i][index]!=flag)
                break;
        }
        if(i<strsSize)
            break;
        flag=strs[0][++index];
    }
    strs[0][index]='\0';
    return strs[0];
}

C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
        string s = strs[0];
        for(int i = 1; i < strs.size(); i++) {
            for(int j = 0; j < s.length(); j++) {
                if(s[j] != strs[i][j]) {
                    s = s.substr(0, j);
                    break;
                }
            }
        }
        return s;
    }
};
上一篇 下一篇

猜你喜欢

热点阅读