Longest Common Prefix in an Array of Strings

Posted by N.K. Chauhan on Mar 31, 2024

Given an array, arr[] of "n" different strings, the task is to find the longest common prefix among all strings present in the array.

Input: {"cup", "cupboard", "cut", "curse"}, Output: "cu"

Input: {"hit", "duper", "super"}, Output: "-1"


Solutions

Method 1: In O(n * length of prefix) time and O(1) space

The idea is to first calculate the length of shortest string, because the common prefix can not exceed the length of shortest string.

Next, start a loop from "0" to "length of shortest string", and in each iteration check if the ith character is same in each string.

If ith character is same in each string, than this character will be part of common prefix.

Else if in any iteration the ith character is different for any string, return substring of any string from 0 to i.

Complexity

The time complexity of this solution is O(n * length of prefix) and space complexity is O(N).

Related


Swap all occurrences of two characters to get lexicographically smallest string

Transform One String to Another with a Minimum Number of Operations

Print all subsequences of a string

Reverse words in a given string

Check whether the given string is a palindrome

Check if two given strings are isomorphic to each other

Print all permutations of a given string

Find all substrings of a string in "O (n^2)" time

Power Set: Print all non-empty subsequences of a string

Check if two strings are equal or not after processing backspace