Longest Common Prefix

Medium Strings

Find the longest common prefix string amongst an array of strings.

Sample input

["flower", "flow", "flight"]

Sample output

Solution

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

print(longest_common_prefix(["flower", "flow", "flight"]))

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

console.log(longestCommonPrefix(["flower", "flow", "flight"]));

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

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
    }
}

fun longestCommonPrefix(strs: Array<String>): String {
    if (strs.isEmpty()) return ""
    var prefix = strs[0]
    for (i in 1 until strs.size) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.dropLast(1)
            if (prefix.isEmpty()) return ""
        }
    }
    return prefix
}

fun main() {
    println(longestCommonPrefix(arrayOf("flower", "flow", "flight")))
}

func longestCommonPrefix(_ strs: [String]) -> String {
    guard var prefix = strs.first else { return "" }
    for s in strs.dropFirst() {
        while !s.hasPrefix(prefix) {
            prefix = String(prefix.dropLast())
            if prefix.isEmpty { return "" }
        }
    }
    return prefix
}

print(longestCommonPrefix(["flower", "flow", "flight"]))

String longestCommonPrefix(List<String> strs) {
  if (strs.isEmpty) return '';
  var prefix = strs[0];
  for (var i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix.isEmpty) return '';
    }
  }
  return prefix;
}

void main() {
  print(longestCommonPrefix(['flower', 'flow', 'flight']));
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string longestCommonPrefix(const vector<string>& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (size_t i = 1; i < strs.size(); i++) {
        while (strs[i].compare(0, prefix.size(), prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    cout << longestCommonPrefix({"flower", "flow", "flight"}) << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

int main() {
    const char *strs[] = {"flower", "flow", "flight"};
    int count = 3;
    char prefix[100];
    strcpy(prefix, strs[0]);
    for (int i = 1; i < count; i++) {
        int j = 0;
        while (prefix[j] && strs[i][j] && prefix[j] == strs[i][j]) j++;
        prefix[j] = '\0';
    }
    printf("%s\n", prefix);
    return 0;
}