[Toggle Comments]
package main // file: impl-004.go import ( "strings" ) func commonPrefix(ss []string, endIndex int) bool { prefix := ss[0][0:(endIndex + 1)] for i := 1; i < len(ss); i++ { current := ss[i] if !strings.HasPrefix(current, prefix) { return false } } return true } // time: O(S * log(m)) — In the worst case, n identical strings of length m, // the algorithm makes log(m) iterations, and in each iteration, // `commonPrefix` does m*n comparisons. (strings.HasPrefix will make m // comparisons, and the `for` loops n times; O((m*n)log(m)) -> O(S log(m)) // // space: O(1) — we don’t use auxiliary space. func lcpBinarySearch(ss []string) string { if len(ss) == 0 { return "" } // Find the shortest length among all the strings. // That’s the upper limit a common prefix will reach at. minLen := MaxInt for _, s := range ss { minLen = min(minLen, len(s)) } // Do a binary search. If there is a matching common prefix on the left half // (i.e., the prefix ends with the middle index), remove the left half of // the search space and continue from the right half (since we are trying // to find the largest prefix and we covered the left half of the search // space already). If there is no common prefix in the left half, remove // the right half, as there is no common prefix ending in the right half // either. low, high := 0, minLen-1 prefixEndIndex := -1 for low < high { mid := (low + high) / 2 if commonPrefix(ss, mid) { // We found a common prefix; let’s store its end index. prefixEndIndex = mid // Let’s try our luck on the right half of the search space too. low = mid + 1 continue // — [1] } // No common prefix on the left half. // Discard the right half of the search space. high = mid - 1 // Observation: // Whenever we move to the next loop iteration (either here or at [1]) // `prefixEndIndex` is always one less than low. // // Also, `low` and `high` eventually converge to the same number. } // We have already computed the `prefixEndIndex`. // Let’s get the common prefix. return ss[0][0 : prefixEndIndex+1] } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */