# 14 - Longest Common Prefix

解法一 - Vertical Scanning (一次比較所有字串的同一 index，再移到下一個 index)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = "";
        if(strs.empty()) return prefix;

        int ind = 0;
        bool findFlag = true;

        while(findFlag) {
            for(int i=0; i<strs.size(); i++) {
                if(ind < strs[i].size() && strs[i][ind] == strs[0][ind]) {
                    if(i == strs.size()-1)
                        prefix += strs[0][ind];
                    continue;
                }
                else {
                    findFlag = false;
                    break;
                }
            }

            ind++;
        }

        return prefix;
    }
};

/*
idea:

use a prefix to record the answer

use an index to record what to compare
while true:
    go through all strings and compare the char at index
    if all the same
        prefix.append(char at the index)
    else(including empty string)
        return prefix

return prefix
*/

Runtime: 8 ms, faster than 75.34% of C++ online submissions for Longest Common Prefix. Memory Usage: 8.8 MB, less than 58.93% of C++ online submissions for Longest Common Prefix.

解法二 - Horizontal Scanning

這種解法滿有趣的，一次只比較兩個兩個字串，找出最大共同 prefix，然後再拿這個最大共同 prefix 去跟下一個字串比，依此類推。

解法三 - Divide and Conquer

Ref

這題的解法有很多種：

1. Leetcode Solution