YukatouArimotou's blog

Can I push_front a char to string in O(1) or O(logn)?
By YukatouArimotou, history, 5 weeks ago, In English

I'm trying to do a problem and i have an idea, but it need to push_front a char to string in O(1) (and for each "push_front" I need to compare two new strings too)!

So...can you tell me how to do it please @@

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YukatouArimotou (previous revision, new revision, compare).

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YukatouArimotou (previous revision, new revision, compare).

→ Reply
»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

use deque of chars. also there is rope which can insert and delete anywhere in O(logn) but with high constant factor.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can I ask the complexity when comparing 2 deques please?

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      O(n)

      And I forgot, if you use hashing you can compare equality in O(1). I think it's better if you post the problem so people can find a better solution

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can use hashing to insert at the beginning in O(1) too.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it -17 Vote: I do not like it

          Is there any hash template that always AC?

          If yes, can I get it please @@

          → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        Sorry but the problem is private so I can't show it here.

        And...I haven't learned hashing yet @@

        Anyway thanks for your help ^^

        → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

create array of length 10^6 or whatever and when you gotta do that operation, change the last element first, then the second last, third last, etc etc

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    but i need to compare 2 strings after each "push_front()" @@

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you can keep a variable that stores the current position. So like say you have the array [0, 0, 0, 0, 0], your variable stores index 4, and then when you compare, you compare everything from index 5 onwards. You push front an "a", then it becomes [0, 0, 0, 0, "a"], variable becomes 3, and you compare everything from 4 onwards.

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hmmm...It can't help in that problem @@

        Anyway thanks for your help ^^

        → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

If you're comparing two strings after doing it, the comparison itself will take $$$\mathcal{O}(n)$$$ time anyway, unless the strings are guaranteed to not be too similar for whatever reason. So there is no point of pushing to the front in $$$\mathcal{O}(1)$$$ when it doesn't decrease the time complexity of performing both operations in the worst case.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok thank you ^^

    Maybe I needa think another idea to solve that problem @@

    → Reply