What should the output be of ["aac", "aabb", "aaba"] ?


  • 1
    B

    The OJ says ["acb"] as wrong answer, and one of the correct solution produces [cba]?


  • 1
    S

    Imagine going through a physical dictionary.

    "The letters within a word are not in a lexicographical order."

    The relative positions of letters in successive words will help us give the order. For the above example

    Compare two words at a time

    1. aac vs. aabb
      first two letters of both words are the same so you can ignore them
      third letter 'c' comes before 'b' - indicates that 'c' comes before 'b' lexicographical in this language
      c -> b (we infer this from the first two words)

    2. aabb vs. aaba
      first three letters of both words are the same so ignore them
      fourth letter 'b' comes before 'a'.
      b - a (we infer this from second and third word)

      Combining (1) and (2) we get the order c - a - b

      Just because 'a' is the first letter of the first word we cannot infer that 'a' is the first letter lexicographically in this language. (I guess that's what caused the confusion in the first place).

    I hope this helps!


  • 0
    B

    Oh yeah!, I finally understood the question, and thanks for the detailed explanation!


  • 0
    S

    looking at the first and second word, c should come before b

    looking at the second and third word. b should come before a.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.