lintcode-78-最长公共前缀

78-最长公共前缀

给k个字符串，求出他们的最长公共前缀(LCP)

样例

在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"

在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"

标签

字符串处理枚举法基本实现 LintCode 版权所有

思路

两两比较公共前缀

code

class Solution {

public:

    /**

     * @param strs: A list of strings

     * @return: The longest common prefix

     */

    string longestCommonPrefix(vector<string> &strs) {

        // write your code here

        int size = strs.size(), i = 0, j = 0;

        if(size <= 0) {

            return string();

        }

        if(size == 1) {

            return strs[0];

        }

        string strA, strB;

        strA = strs[0];

        for(i=1; i<size; i++) {

            strB = strs[i];

            string strLCP;

            for(j=0; j<strA.size() && j<strB.size(); j++) {

                if(strA[j] == strB[j]) {

                    strLCP += strA[j];

                }

                else{

                    break;

                }

            }

            strA = strLCP;

        }

        return strA;

    }

};

巴特西

lintcode-78-最长公共前缀

78-最长公共前缀

样例

标签

思路

code

最新文章

热门文章