problem-solved's blog

can anyone help me with this problem (string problem)
By problem-solved, 12 years ago, In English

this problem

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

Well, an interesting problem...

But I've mistaken with the solution: we should use a DP instead.

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

    maybe you are right ，but it's still hard for me to think in that direction (DP)

    → Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it +2 Vote: I do not like it

You can solve it using DP. We trying to construct a palindrome, but we didn't know it's length. We know some prefix, and we interested only in it's last 7 characters, reversed prefix is suffix because it's palindrome. Each time we trying to add some string into prefix or into suffix. this string must be first unused (or last). we have to remember for each side (prefix and suffix) where was added string at previous step, to prevent "collisions" — situations when two strings coincide. State of dp is 7 last characters of prefix (it's reverse is prefix of suffix), index of first unused string, index of last unused string, and two additinal boolean parameters). Also, don't forget about situation when string placed into the middle of the palidrome, you can try to combine suffix and prefix, after described DP. parameter "7 last characters" can be only one of string from input, or it's reverse.
UPD: Described idea has complexity O(N^3), maybe we should use Dijkstra, to increase perfomance
UPD2: I was wrong, actually it's complexity is O(N^2) because for each (beginStr, lastStr) there is constant number of possible strings to be prefix.
UPD3: my solution

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    what's cL and cR in your code

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      "we have to remember for each side (prefix and suffix) where was added string at previous step, to prevent “collisions” — situations when two strings coincide" cL == 1 iff there was string at very left of prefix (s), so we cannot add next string at pos = 0 (i = 0).

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        thank you , well I almost understand the solution except the "cL",I can't think it clearly ,can you show me an example about the use of cL ,maybe an example is helpful for me to understand ,thanks again

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it +2 Vote: I do not like it

          look at second sample — "abcdefg abcdefg".
          L = 0, R = 2, s = "0123456"
          at first step add abcdefg to the prefix at i=7.
          L = 1, R = 2, s = "abcdefg"
          you can't add next "abcdefg" at i=0, and go to L = 2, R = 2 because in this case answer will be abcdefgfedcba (both strings starts at the same place(at very begin of the string), but k[i] must be strictly less than k[i + 1].
          another sample "abcdefg gfedcba" now you CAN add first string to the left, and then second string to the right. anwser abcdefgfedcba.

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          prefix and it's reverse marked bold
          string added at previous step underlined

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            I still can't figure it out that why do you write (cR && i==0) its' the only question I have now

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
              ← Rev. 4   Vote: I like it 0 Vote: I do not like it

              i don't know why name of variable is "cL", but you can read it as "can't to put string at very left". if cL == 1, you can't. if cL == 0 you can. look at picture again.
              line 2: L = 1, R = 5, cL = 1, cR = 0
              line 3: L = 1, R = 4, cL = 1, cR = 1
              when we add string "bbbbaaa" to the right side at pos = 0 (i = 0), we should remember we still can't place string at left side. i.e. cL && i == 0.

              → Reply