LeetCode14. Longest Common Prefix（模拟 ）

LeetCode14. Longest Common Prefix（模拟 ）

• Easy
• Accepted：547,429
• Submissions：1,602,744

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

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

链接

https://leetcode.com/problems/longest-common-prefix/

题意

输出给定的所有字符串的最长公共前缀。

题解

就一模拟，我是先找出最短的那个字符串，然后挨个比较，字符串数量n，最短的字符串长度为m，那么时间复杂度$O(n*m)$。注意输入为空的情况。

代码

• Runtime: 8 ms, faster than 54.24% of C++ online submissions for Longest Common Prefix.
• Memory Usage: 8.7 MB, less than 98.39% of C++ online submissions for Longest Common Prefix.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        if (n == 0) // 注意
            return "";
        int len = strs[0].length(), id = 0;
        for (int i = 1; i < n; ++i)
        {
            if (strs[i].length() < len)
            {
                len = strs[i].length();
                id = i;
            }
        }
        bool flag = true;
        int ans = 0;
        for (int i = 0; i < len && flag; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (strs[j][i] != strs[id][i])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
                ++ans;
        }
        return strs[id].substr(0, ans);
    }
};

The end.
2019年9月25日 星期三