Link to Question

EASY

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example

Input:

strs = ["flower","flow","flight"]

Output:

"fl"

Input:

strs = ["dog","racecar","car"]

Output:

""

Explanation:
There is no common prefix among the input strings.

---

Constraints

• 1 ≤ strs.length ≤ 200
• 0 ≤ strs[i].length ≤ 200
• strs[i] consists of only lowercase English letters.

---

Solution: Vertical Scanning

• Time Complexity: O(S), where S is the sum of all characters in all strings.
• Space Complexity: O(1), as only a constant amount of extra space is used.

C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 1)   return strs.back();
        int i = 0;
        while(1) {
            for (int j = 1; j < strs.size(); j++)
                if (i >= strs[j].size() || i >= strs[j-1].size() || strs[j][i] != strs[j-1][i])
                    return strs[0].substr(0, i);
            i++;
        }
        return strs[0].substr(0, i);
    }
};