Longest Common Prefix

Easy

Python

def longest_common_prefix(strs):
    if not strs: return ''
    p=strs[0]
    for s in strs[1:]:
        while not s.startswith(p):
            p=p[:-1]
            if not p: return ''
    return p

Java

public String longestCommonPrefix(String[] strs){
    if(strs.length==0) return "";
    String p=strs[0];
    for(int i=1;i<strs.length;i++)
        while(!strs[i].startsWith(p)){
            p=p.substring(0,p.length()-1);
            if(p.isEmpty()) return "";
        }
    return p;
}

Key Insight

p[:-1] vs substring(0,len-1). Truthiness vs isEmpty().

Python → Java Differences

p[:-1] slicing vs substring()
'not p' vs isEmpty()
Shrink-until-match identical

Python

def longest_common_prefix(strs):
    if not strs: return ''
    p=strs[0]
    for s in strs[1:]:
        while not s.startswith(p):
            p=p[:-1]
            if not p: return ''
    return p

Java

public String longestCommonPrefix(String[] strs){
    if(strs.length==0) return "";
    String p=strs[0];
    for(int i=1;i<strs.length;i++)
        while(!strs[i].startsWith(p)){
            p=p.substring(0,p.length()-1);
            if(p.isEmpty()) return "";
        }
    return p;
}

Algorithm Steps

1. Start with first string
2. Shrink until all match

← Previous All Strings Next →