The key observation is that you only look at a byte once.
On Thu, Feb 27, 2020, 22:49 Amnon Baron Cohen <amno...@gmail.com> wrote:
> 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 golan...@googlegroups.com.
>> > 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 golang-nuts+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/18eb08a5-f2be-452b-a31f-9643932fc4bd%40googlegroups.com
> <https://groups.google.com/d/msgid/golang-nuts/18eb08a5-f2be-452b-a31f-9643932fc4bd%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
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 golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CAGrdgiXMyCTZhNQniRmf9G3SUEqwZY%3D4exDCD7ZrEPUk8QJ5XQ%40mail.gmail.com.
