[数据结构与算法]14.最长公共前缀-LeetCode

1.问题描述

这里直接采用的是leetcode上面的问题描述

????????编写一个函数来查找字符串数组中的最长公共前缀。

????????如果不存在公共前缀，返回空字符串 ""。

下面给出示例：

2.解题思路

首先我们思考什么为最长公共前缀，在一个字符串数组中找到最长公共前缀，有什么特殊的情况。

• ? ? ? ? 空字符串数组返回""。
• ? ? ? ? 字符串数组只有一个字符串时，那么最长公共前缀就是这个字符串本身。
• ? ? ? ? 最长公共前缀应该是小于等于字符串数组中最短的那个字符串。

有了这些条件那么我们解题起来就比较清晰了。

????????这里我的方法无法比较第二种特殊情况，但是我在开始的时候判断字符串数组长度是否为1，如果字符串数组长度为1的话，直接返回该字符串。

????????我这里采用的是两两较方法，字符串数组的相邻的两个字符串的首字符两两进行比较，如果有任一对字符串首字符不相等，那么就说明无最长公共前缀，如果比较到了末尾字符串首字符全部相等的话，那么就将此字符保存起来，重复上面的比较操作直至字符串字符比较不相等，就返回已经保存的字符串。

这里举个栗子：strs = ["flower","flow","flight"]

首先找到最短的字符串长度，上面最短的为"flow" 是4

那么我们比较的时候只比较到第四个元素比如"flower"，我们只比较了"flow"，后面的不用看了。

1. ?第一轮："flower"的 f 与"flow"的 f 相比较返回的是true，继续"flow"的 f 与?"fflight"的 f 比较返回也是true。此时比较到了末尾了，将 f 保存起来。
2. 第二轮："flower"的 l?与"flow"的 l?相比较返回的是true，继续"flow"的 l?与?"flight"的 l?比较返回也是true。此时比较到了末尾了，将 l?保存起来。
3. 第三轮："flower"的 o?与"flow"的 o?相比较返回的是true，继续"flow"的 o?与?"flight"的 i?比较返回也是false。此时没有比较到末尾，直接返回"fl"。

上述为思想。

3.代码实现

bool compareChar(char a,char b){
        if(a == b){
            return true;
        }
        return false;
    }
    string longestCommonPrefix(vector<string>& strs) {
        if(!strs.size()){
            return "";
        }
        if(strs.size() == 1){
            return strs[0];
        }
            int n=0;
            string CommonStr = "";
            int minStrsLength = 200;
            for(string item:strs){
                minStrsLength = min((int)item.size(),minStrsLength);
            }
            for(int n = 0; n<minStrsLength; n++){
                int k = 0;
                while(k < strs.size()-1){
                    if(compareChar(strs[k][n],strs[k+1][n])){
                        k++;
                    }else{
                        return CommonStr;
                    }
                    if(k == strs.size()-1){
                        CommonStr+=strs[0][n];
                    }
                }
            }
            return CommonStr;
    }