Question

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

Answer 1

package main

import (
    "fmt"
    "regexp"
    "strings"
)

// Extract alphabetic words (lowercased)
func extractWords(text string) []string {
    re := regexp.MustCompile(`[A-Za-z]+`)
    matches := re.FindAllString(text, -1)

    words := make([]string, 0, len(matches))
    for _, m := range matches {
        words = append(words, strings.ToLower(m))
    }
    
    return words
}

// Build prefix → list of words that share that prefix
func groupByPrefixes(words []string) map[string][]string {
    groups := make(map[string][]string)

    for _, w := range words {
        for i := 1; i <= len(w); i++ {
            prefix := w[:i]
            groups[prefix] = append(groups[prefix], w)
        }
    }

    return groups
}

// Find the longest prefix that appears in 2+ words
func longestSharedPrefix(groups map[string][]string) string {
    best := ""

    for prefix, list := range groups {
        if len(list) >= 2 && len(prefix) > len(best) {
            best = prefix
        }
    }

    return best
}

func main() {
    text := "The Lowly inhabitants of the lowland were surprised to see " +
        "the lower branches of the trees."

    words := extractWords(text)
    groups := groupByPrefixes(words)
    prefix := longestSharedPrefix(groups)

    if prefix != "" {
        group := groups[prefix]
        fmt.Println("Longest shared prefix:")
        fmt.Printf("%s | prefix_len=%d | group_count=%d | %v\n",
            prefix, len(prefix), len(group), group)
    } else {
        fmt.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