Solve Leetcode Problems and Get Offers From Your Dream Companies

LeetCode 14 | Longest Common Prefix (Easy)

Nil Madhab
Jan 23 · 4 min read

This story was originally published at simplecoding.dev

Motivation to Learn Algorithms

Problem Statement

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.

Sample Input

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

Let's get Started

What is Prefix

A prefix of a string is any substring that starts from the first character. The number of different prefixes of a string is equal to its length. For example, the string “flower” will have 6 different prefixes:

f
fl
flo
flow
flowe
flower

Observation

Is there any upper limit on the length of our answer string?

flower
flow
flowchart
In this the upper limit on LCP length is 4, and the length of answer is also 4
Answer = flow
flower
flow
flag
In this the upper limit on LCP length is 4, but the length of answer is 2
Answer = fl

Solution

Let minLen be the length of the smallest string. So from our observation, we can conclude that while finding the LCP we have to only consider the first minLen characters of every string.

Code in Java:

Code in C++:

Time and Space Complexity

The time complexity of our solution is O(n*m), where n is the size of strs array and m is the length of the longest string in our array. In the worst case, we may have to check every character of all the strings. For example, we may have an array in which all the strings are equal.

Practice Makes Perfect

Can this problem be solved using a Trie data structure? Think about it.

Thank You for reading and Follow this publication for more Leetcode Solutions!😃

Javarevisited

Medium’s largest Java publication, followed by 10000+ programmers. Follow to join our community.

Sign up for Javarevisited Newsletter

By Javarevisited

Collection of best Java articles, tutorials, courses, books, and resources from Javarevisite and its authors, Java Experts and many more.  Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Nil Madhab

Written by

Developer @Booking.com | ex: Samsung, OYO | IIT Kharagpur | Entrepreneur, founder of simplecoding.dev | connect me https://twitter.com/Nilmadhabmondal

Javarevisited

A humble place to learn Java and Programming better.

Nil Madhab

Written by

Developer @Booking.com | ex: Samsung, OYO | IIT Kharagpur | Entrepreneur, founder of simplecoding.dev | connect me https://twitter.com/Nilmadhabmondal

Javarevisited

A humble place to learn Java and Programming better.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store