Question

How to find the longest common prefix of all the words in a string with Java

Answer 1

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LongestCommonPrefix {

    // Extract lowercase alphabetic words
    static List<String> extractWords(String s) {
        List<String> words = new ArrayList<>();
        StringBuilder current = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                current.append(Character.toLowerCase(c));
            } else if (current.length() > 0) {
                words.add(current.toString());
                current.setLength(0);
            }
        }

        if (current.length() > 0) {
            words.add(current.toString());
        }

        return words;
    }

    // LCP of two strings
    static String lcpTwo(String a, String b) {
        int i = 0;
        while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) {
            i++;
        }
        return a.substring(0, i);
    }

    // LCP of ALL words (Python-style)
    static String longestCommonPrefix(String s) {
        List<String> words = extractWords(s);
        if (words.isEmpty()) return "";

        Collections.sort(words);

        return lcpTwo(words.get(0), words.get(words.size() - 1));
    }

    public static void main(String[] args) {
        String s1 = "The lowly inhabitants of the lowland were surprised to see the lower branches.";
        System.out.println("LCP: '" + longestCommonPrefix(s1) + "'");  // ""

        String s2 = "unclear, uncertain, unexpected";
        System.out.println("LCP: '" + longestCommonPrefix(s2) + "'");  // "un"
    }
}



/*
run:

LCP: ''
LCP: 'un'

*/

 

70+ SQL courses for beginners and professionals

Answer 2

public class LongestCommonPrefix {

    public static String longestCommonPrefix(String input) {
        if (input == null || input.isEmpty()) return "";
    
        // Split by non-word characters to get clean tokens
        String[] words = input.toLowerCase().split("\\W+");
        if (words.length == 0) return "";
    
        // Start with the first word as the potential prefix
        String prefix = words[0];
    
        for (int i = 1; i < words.length; i++) {
            // Shorten the prefix until it matches the start of the current word
            while (words[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }


    public static void main(String[] args) {
        String s1 = "The lowly inhabitants of the lowland were surprised to see the lower branches.";
        System.out.println("LCP: '" + longestCommonPrefix(s1) + "'");  // ""

        String s2 = "unclear, uncertain, unexpected";
        System.out.println("LCP: '" + longestCommonPrefix(s2) + "'");  // "un"
    }
}



/*
run:

LCP: ''
LCP: 'un'

*/

 

70+ SQL courses for beginners and professionals