[Toggle Comments]
package main // file: impl-005.go import ( "fizzbuzz/trie" ) func longestPrefix(t trie.Trie, first string) string { // The other strings are already in the trie. We have augmented the trie // implementation in [1] and added a `SearchLongestPrefix()` method. // // [1]: https://fizzbuzz.pro/pro/208-implement-trie/pages/doc.go.html return t.SearchLongestPrefix(first) } // Since we are working with common prefixes and searching for them, a trie can // be a choice to explore. It might prove itself to be performant, too if you // generate the trie once and cache it. func lcpTrie(ss []string) string { if len(ss) == 0 { return "" } if len(ss) == 1 { return ss[0] } // For a trie implementation, see [1] above. // // If we can cache this trie and reuse it, it can prove to be efficient. // However, if we are going to create a new trie at each computation, // then the efficacy of using a Trie is debatable since creating a // trie is not cheap. lcpTrie := trie.New() prefix := ss[0] rest := ss[1:] // Prepare the Trie first. for _, s := range rest { lcpTrie.Insert(s) } // #region boundary check if rest == nil { return "" } if len(rest) == 0 { return "" } // #endregion return longestPrefix(*lcpTrie, prefix) } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */