This problem focuses on finding the longest common prefix string shared among an array of strings. If no common prefix exists, the result should be an empty string.
Steps
- Initialize a pointer
xto track character positions in the first string. - Iterate through each character of the first string using
whileloop. - For every character at position
xin the first string, compare it with the character at the same position in the other strings. - If a mismatch is found or if the current index exceeds the length of any string, return the substring from the first string from 0 to
x. - If the loop completes without any mismatch, return the first string entirely (it is the common prefix).
Dry Run
Input: ["flower", "flow", "flight"]
x = 0: Compare ‘f’ with all → matchx = 1: Compare ‘l’ → matchx = 2: Compare ‘o’ vs ‘i’ → mismatch- Return
"fl"
Time & Space Complexity
- Time Complexity: O(n·m), where
nis the number of strings andmis the length of the shortest string - Space Complexity: O(1), as no extra space is used apart from variables
var longestCommonPrefix = function(strs) {
let x = 0;
while (x < strs[0].length) {
let ch = strs[0][x];
for (let i = 1; i < strs.length; i++) {
if (ch != strs[i][x] || x == strs[i].length) {
return strs[0].substring(0, x);
}
}
++x;
}
return strs[0];
};
#include <iostream>
#include <vector>
using namespace std;
string longestCommonPrefix(vector<string>& strs) {
int x = 0;
while (x < strs[0].length()) {
char ch = strs[0][x];
for (int i = 1; i < strs.size(); i++) {
if (x == strs[i].length() || ch != strs[i][x]) {
return strs[0].substr(0, x);
}
}
++x;
}
return strs[0];
}
#include <stdio.h>
#include <string.h>
char* longestCommonPrefix(char strs[][100], int strsSize) {
static char prefix[100];
int x = 0;
while (1) {
char ch = strs[0][x];
for (int i = 1; i < strsSize; i++) {
if (x >= strlen(strs[i]) || strs[i][x] != ch) {
prefix[x] = '\0';
return prefix;
}
}
prefix[x] = ch;
x++;
}
}
public class Solution {
public String longestCommonPrefix(String[] strs) {
int x = 0;
while (x < strs[0].length()) {
char ch = strs[0].charAt(x);
for (int i = 1; i < strs.length; i++) {
if (x == strs[i].length() || ch != strs[i].charAt(x)) {
return strs[0].substring(0, x);
}
}
x++;
}
return strs[0];
}
}
def longestCommonPrefix(strs):
x = 0
while x < len(strs[0]):
ch = strs[0][x]
for i in range(1, len(strs)):
if x == len(strs[i]) or strs[i][x] != ch:
return strs[0][:x]
x += 1
return strs[0]
1 Comment
Add Problem statements here for revision purpose