【打卡】牛客网：BM84 最长公共前缀

自己写的：

题目要求时间复杂度是o(n*len)，说明可以遍历所有的字符。

空间复杂度o(1)，说明不能用字符串存储公共前缀，所以用下标来记录。

调试过程：

大概花了20min。

我调试前的做法是，在while循环中，从后往前遍历，用的j--。但是没有考虑到第0个字符串长度很小的问题。所以改成了j++。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param strs string字符串vector * @return string字符串*/string longestCommonPrefix(vector<string>& strs) {// write code here int ans = 100000; //粗心，错误示范：ans = 0int n = strs.size();cout<<"n"<<n<<endl;if(n == 0)return "";if(n == 1)return strs[0];for(int i = 1; i < n; i++){int j = 0; while(j < strs[0].size() && j < strs[i].size() && strs[0][j] == strs[i][j]) // 第0个字符串长度可能很小j++;// j为相同字符串的位置的后一个，或者为两个字符串中，短的字符串的长度   ans = min(ans, j); }return strs[0].substr(0, ans); //粗心，左闭右开！}
};

模板的：

 我采用的是，第一个字符串和后面每个字符串，二者逐次比较，即二者逐个字符进行比较。

模板的是，针对每个字符，从前往后，比较所有的字符串是否相同。

时间复杂度都是o(n*len)。