Leetcode 14: Longest Common Prefix

Leetcode 14: Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.

题目大意: M 个  string 组成的array, 求这些string的最长公共前缀

分析： 一般求最大，最小，有几种算法： 1. 直接求， 暴力解法。 2. DP 3. Best first search
这题需要一一比较每个字符串中的每一个字符，找到一个不相等就return， 否则，每个string的index 都往后移动一位。这样的计算过程，让我联想到merge K sorted array/list这种用Best first search 来求解的题目，initial state 放进priority_queue，然后进行expand_rule来对priority_queue进行操作，控制每个index移动。 但是这题不需要priority_queue,因为不需要比大小，只要各位的char相等，就必须都向后移，不需要控制index的移动，根据这样的特点，其实只要一个变量控制index 位置的移动，需要用一个for loop来检测每个string在index的位置是否相等。
一开始想看看有没有更加优化的方法，但是觉得这个题目最优解就只有o(N*M)的时间复杂度
//O(N * M)
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string rst = "";
        //sanity check
        if (strs.size() == 0) return rst;
        if (strs.size() == 1) return strs[0];
        for (int j = 0;; 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])) {
                continue;
            } else {
                return strs[i].substr(0, j);
            }
        }
        return rst;
    }
};


updated:

对于一眼上看去不知道题目属于哪个类型，用什么算法解的题目，首先提供给面试官暴力的解法， 然后想下时间空间复杂度， 比不会做好
暴力解法： O（n*m）
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //sanity checkn
        if (strs.size() == 0) return "";
        for (int i = 0; i < strs[0].size(); i++) {
            char tmp = strs[0][i];
            for (int j = 1; j < strs.size(); j++) {
                if (tmp != strs[j][i]) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};