Question

How to find the longest shared prefix among all words in a string with Java

Answer 1

import java.util.Map;
import java.util.List;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class LongestSharedPrefix {

    // Extract alphabetic words (case-insensitive)
    static List<String> extractWords(String s) {
        List<String> words = new ArrayList<>();
        Matcher m = Pattern.compile("[a-zA-Z]+").matcher(s);

        while (m.find()) {
            words.add(m.group().toLowerCase());
        }
        return words;
    }

    // Build a map: prefix -> list of words having that prefix
    static Map<String, List<String>> groupByAllPrefixes(List<String> words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String w : words) {
            for (int i = 1; i <= w.length(); i++) {
                String prefix = w.substring(0, i);
                groups.computeIfAbsent(prefix, k -> new ArrayList<>()).add(w);
            }
        }
        return groups;
    }

    // Find the longest prefix that appears in 2+ words
    static String findLongestSharedPrefix(Map<String, List<String>> groups) {
        String best = "";

        for (Map.Entry<String, List<String>> e : groups.entrySet()) {
            String prefix = e.getKey();
            List<String> ws = e.getValue();

            if (ws.size() >= 2 && prefix.length() > best.length()) {
                best = prefix;
            }
        }
        return best;
    }

    public static void main(String[] args) {

        String s = "The Lowly inhabitants of the lowland were surprised to see "
                 + "the lower branches of the trees.";

        List<String> words = extractWords(s);
        Map<String, List<String>> groups = groupByAllPrefixes(words);

        String longest = findLongestSharedPrefix(groups);

        if (!longest.isEmpty()) {
            System.out.println("Longest shared prefix:");
            System.out.println(longest + " | prefix_len=" + longest.length()
                    + " | group_count=" + groups.get(longest).size()
                    + " | " + groups.get(longest));
        } else {
            System.out.println("No shared prefix found.");
        }
    }
}



/*
run:

Longest shared prefix:
lowl | prefix_len=4 | group_count=2 | [lowly, lowland]

*/

 

70+ SQL courses for beginners and professionals