Longest Common Prefix — Leetcode #14

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 "".

Problem explanations:

The questions ask us to find the longest common prefix, prefix is a word that can be added at the beginning of the string to form a new word. We have given a vector of strings from which we have to find the prefix and we have to return a string of the longest common prefix.

problem links: leetcode, geekforgeeks.

Example 1:

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

Example 2:

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

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

Solution

• C++ solution

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

• Java Solution

    class Solution {
        public String longestCommonPrefix(String[] strs) {
            String ans = "";
            int n = strs.length;
  
            int j = 0;
            while (j < strs[0].length()) {
                for (int i = 1; i < n; i++) {
                    if (strs[0].charAt(j) != strs[i].charAt(j)) {
                        return ans;
                    }
                }
                ans += strs[0].charAt(j);
                j++;
            }
  
            return ans;
        }
    }
  

Explanation:

The solution uses a simple approach that iterates over the vector of strings.

A string is declared ans to store the common prefix and n is used to store the size of the vector.

we want the outer loop to run till the size of the first string in the vector. The inner for loop will compare the character of the first string’s char at index j with the strings in the vector at index i and char at index j.

If the characters don’t match then we return the ans, this is the longest common prefix that is present. if the loop end with encountering the condition we add that character in the ans and increment j by

Time Complexity

If m is the size of the first string and n is the size of the list of strings. Then the worst-case time complexity will be O(m x n).

Space Complexity

The space complexity of this solution is O(1) or constant space complexity.

The solution uses a string ans to store the ans and variable n to store the size of the list. No additional data structures are used for the solution.

---

Thank you for reading the post, I hope this would have helped you to understand the question better and the solution helped you to get a clear understanding of the approach used.

Feel free to drop any comments, I would have to solve your queries and improve my solution.