Leetcode: 14. Longest Common Prefix (Vertical Scanning)

Vertical Scanning Approach: Finding Longest Common Prefix Among an Array of Strings

Problem Statement

Given an array of strings strs, our task is to find the longest common prefix among all the strings. If there is no common prefix, we should return an empty string "".

For example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

In this case, the longest common prefix among the strings "flower," "flow," and "flight" is "fl".

Input: strs = ["dog","racecar","car"]
Output: ""

Here, there is no common prefix among the strings, so we return an empty string.

Solution Approach: Vertical Scanning

We can approach this problem using the vertical scanning technique. We start by comparing the characters at the same index from left to right in all the strings. If at any point, the characters differ or we reach the end of any string, we return the substring up to that index as the longest common prefix.

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

Example Scenarios

Let's go through a few example scenarios to understand the solution better.

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

We start comparing the characters at index 0 in all the strings. The character 'f' is common, so we move to index 1. The character 'l' is common, so we move to index 2. The character 'o' is common, so we move to index 3. At this point, we reach the end of the string "flow", so we return the substring "flo" as the longest common prefix.

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

Here, the character 'd' is common at index 0. However, at index 1, the characters differ. So, we return an empty string as there is no common prefix among the strings.

Conclusion

In this blog post, we explored the vertical scanning approach for finding the longest common prefix among an array of strings. By comparing the characters at the same index from left to right in all the strings