[Toggle Comments]
package main // file: impl-001.go import ( "strings" ) // Intuition: If A and B have a longest common prefix P, then C will have either // the same common prefix or smaller subset of P. // // In other words: Given L = LCP(A, B); LCP(A, B, C) = LCP(L, C) // // We can generalize this. // // time: O(S) (where S is sum of all chars in all strings) // (assume n equal strings of length m; then you’ll make m*n comparisons) // // space: O(1) func lcpHorizontalScan(ss []string) string { if len(ss) == 0 { return "" } prefix := ss[0] for i := 1; i < len(ss); i++ { cur := ss[i] // While there is no match, shrink the prefix candidate. // If there is a match, continue with the next string. for strings.Index(cur, prefix) != 0 { prefix = prefix[0 : len(prefix)-1] // No suitable prefix anymore, no need to search further. if len(prefix) == 0 { return "" } } } return prefix } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */