You are right.
I had wrongly assumed that utf8.DecodeLastRuneInString has O(n) runtime.
But it has constant runtime as it reads at most 4 bytes at the end of the
string.
On Thursday, 27 February 2020 21:47:19 UTC, kortschak wrote:
>
> Why? There's a single correctly sized allocation made up front and then
> a linear time walk along the encoded runes with truncation after each
> rune.
>
> On Thu, 2020-02-27 at 13:05 -0800, Amnon Baron Cohen wrote:
> > O(n^2)
> >
> > On Thursday, 27 February 2020 18:53:01 UTC, rog wrote:
> > > If you really just want to reverse rune-by-rune, it's pretty
> > > straightforward:
> > >
> > > func Reverse(s string) string {
> > > r := make([]byte, 0, len(s))
> > > for len(s) > 0 {
> > > _, n := utf8.DecodeLastRuneInString(s)
> > > i := len(s) - n
> > > r = append(r, s[i:]...)
> > > s = s[:i]
> > > }
> > > return string(r)
> > > }
> > >
> > > That will also deal correctly with invalid utf8 encoding - all the
> > > bytes of the original string will be present in the result.
> > > >
> >
> > --
> > You received this message because you are subscribed to the Google
> > Groups "golang-nuts" group.
> > To unsubscribe from this group and stop receiving emails from it,
> > send an email to [email protected] <javascript:>.
> > To view this discussion on the web visit
> >
> https://groups.google.com/d/msgid/golang-nuts/2333bc33-8740-4f8b-972e-37d2d60b9dc7%40googlegroups.com
>
> > .
>
>
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/18eb08a5-f2be-452b-a31f-9643932fc4bd%40googlegroups.com.
