[LintCode] Longest Common Prefix 最长共同前缀

简介:

Given k strings, find the longest common prefix (LCP).

For strings "ABCD""ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG""ABCEFG" and "ABCEFA", the LCP is "ABC"

LeetCode上的原题,请参见我之前的博客Longest Common Prefix

解法一:

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.empty()) return "";
        string res = "";
        for (int j = 0; j < strs[0].size(); ++j) {
            char c = strs[0][j];
            for (int i = 0; i < strs.size(); ++i) {
                if (j >= strs[i].size() || strs[i][j] != c) return res;
            }
            res.push_back(c);
        }
        return res;
    }
};

解法二:

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.empty()) return "";
        for (int j = 0; j < strs[0].size(); ++j) {
            for (int i = 0; i < strs.size() - 1; ++i) {
                if (j >= strs[i].size() || j >= strs[i + 1].size() || strs[i][j] != strs[i + 1][j]) {
                    return strs[i].substr(0, j);
                }
            }
        }
        return strs[0];
    }
};

本文转自博客园Grandyang的博客,原文链接:最长共同前缀[LintCode] Longest Common Prefix ,如需转载请自行联系原博主。

相关文章
|
人工智能 算法
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
|
人工智能 测试技术
PAT (Basic Level) Practice (中文) B1008 数组元素循环右移问题 (20 分)
PAT (Basic Level) Practice (中文) B1008 数组元素循环右移问题 (20 分)
110 0
PAT (Basic Level) Practice (中文) B1008 数组元素循环右移问题 (20 分)
|
人工智能 vr&ar
Atcoder--Candy Distribution II--前缀和+map
题目描述 There are N boxes arranged in a row from left to right. The i-th box from the left contains Ai candies. You will take out the candies from some consecutive boxes and distribute them evenly to M children. Such being the case, find the number of the pairs (l,r) that satisfy the following:
110 0
LeetCode之Longest Common Prefix
LeetCode之Longest Common Prefix
113 0
# Leetcode 14:Longest Common Prefix 最长公共前缀
公众号:爱写bug 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 "". 编写一个函数来查找字符串数组中的最长公共前缀。
1006 0
|
C++ Windows Java
[LeetCode] Longest Absolute File Path 最长的绝对文件路径
Suppose we abstract our file system by a string in the following manner: The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.
1599 0