[Toggle Comments]
package main // file: impl-003.go func lcpDq(left, right string) string { ml := min(len(left), len(right)) for i := 0; i < ml; i++ { if left[i] != right[i] { return left[0:i] } } return left[0:ml] } func lcpDqHelper(ss []string, l int, r int) string { if l == r { return ss[l] } mid := (l + r) / 2 left := lcpDqHelper(ss, l, mid) right := lcpDqHelper(ss, mid+1, r) return lcpDq(left, right) } // LCP is associative: LCP(S1…Sn) == LCP(LCP(S1…Sk), LCP(Sk+1…Sn)). // Therefore, we can use a divide-and-conquer technique. // // time: O(S) where S=m*n (n equal string with length m) // // space: O(m log(n)) — (log(n) recursive calls, each call needs m space // to store the result. This assumes we are running all recursive calls // in parallel, otherwise it should be O(log(n))) func lcpDivideAndConquer(ss []string) string { if len(ss) == 0 { return "" } startIndex := 0 endIndex := len(ss) - 1 return lcpDqHelper(ss, startIndex, endIndex) } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */