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
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.
Auto comment: topic has been updated by vd__coder (previous revision, new revision, compare).
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)$$$.
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
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)
Here is the implemented code in C++, read if you need help in understanding such implementation details.
, 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.
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!
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)$$$.
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.
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.
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.