vd__coder's blog

By vd__coder, history, 2 years ago, In English

Consider a matrix of size n, consisting of lower case aplhabets. We are required to find lexicographically smallest string starting from (1,1) and ending at (n,n).From any cell (i,j) we can either go right or down.

Now it is easily solvable in O(n^3) time ans space , but it is required to solve it in O(n^2) both time and space. Any help is appreciated

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

question: is this a general graph or a DAG? in other words, can we move only from $$$(i,j)$$$ to $$$(i+1,j)$$$ and $$$(i,j+1)$$$, or all 4 adjacent cells? I think this is a greedy problem, but we need some information at least.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

solution after edit: you may notice, from the matrix we get $$${2n-2}\choose{n-1}$$$ strings, each of length $$$2n-1$$$. Now think of the graph like a trie. you can then traverse the graph greedily to find the lexicographically smallest string. remember though, there may be multiple cells with the same prefix, so you may need to use BFS for this problem. the worst case is when all alphabets in the grid are the same, giving time complexity of $$$O(n^2)$$$.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Say i use bfs, (1,1) as root as then subsequent graph is formed , from a node (i,j) i would go its that child which has smaller character, but in case those characters are same, i would be requiring to return string by those cells with same characters. wont this be n^3??

    It would be really great if you can explain in some detail

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      it's just implementation detail, but you can reject cells where the current cell's alphabet is bigger than the ones in the same index found so far. refer to the drawing for a graphical representation.

      here is a case of the same problem where you need to find the lexicographically largest string on a tree. (it's in korean so you may need a translator)

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

        Here is the implemented code in C++, read if you need help in understanding such implementation details.

        Code
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        , got it, since we can go only right and down, when plotting grid as a graph, we can't go to a cell that is rejected above, This was the point I missed.

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

      It is obvious that you will visit a cell at most once. This is because every time you go right or down, your manhatten distance relative to $$$(1,1)$$$ increases by $$$1$$$ unit. So, if you have visited a cell, you won't ever visit the cell again!

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm thinking along the lines of-
1. Replace all lowercase alphabets with Integer Values $$$(0 - 25)$$$.
2. Then the problem reduces to finding the minimum path sum from $$$(1, 1)$$$ to $$$(n, n)$$$.

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

    This is no such simple problem — approaching it as a shortest distance problem should give you many issues in the process. For example, how do we convert the distance to the original string? Is $$$\text{dcba}$$$ treated equal to $$$\text{abcd}$$$? Sure, you can use dijkstra with some major alterations in the graph, but this would be too inefficient and meaningless.

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

      That's a good point you pointed out.

      Lets say I have a string $$$str="a...z"$$$, with each character appearing exactly once and in lexicographic order. $$$str[0]$$$ gives $$$a$$$ and $$$str[25]$$$ gives $$$z$$$.
      We start with an empty string and based on the number we encounter, we can append $$$str[num]$$$ to the string.

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How does this improve understanding/solving the problem over the BFS solution already stated above? Along with the already stated issues, your solution may require understanding the string as a base-$$$26$$$ integer, which only makes the problem more complex.