I was going through some coding exercises, and had some trouble with a question to implement a function to uniformize a directory path.
Example:
Input: /dir1/dir2/../dir3/file.txt
Output: /dir1/dir3/file.txt
We could use a stack to solve this problem in O(n) time/space complexity. But we don't want to use extra space.
How could we solve this problem with O(1) space complexity? I am struggling with an in-place solution.
I would think, not having written it, that you can get buy with an extra pointer. Since in the end, you're mostly doing just shifts, you can simply have one pointer representing you current place scanning the string, and then other pointer as a destination place within the string. The key is that you actively consume the string as you go.
For example:
/dir1/dir2/../dir3/file.txt
When you hit the .., your "current pointer" remains on the / of /dir3.
You then use the destination pointer to scan backwards from the .. up to the / of /dir2.
Once you have the destination pointer done, you shift everything from the current pointer (the / of /dir3) up in the string, adjusting the current pointer as you go.
Then you rinse and repeat until you're done. Same thing happens with a /./ path. Just consume it in place similarly.
You could just use the destination pointer in the interim to note the start of the current token, but basically you just do a bunch of scanning up and down the string as you shift it around in place.
That's just a guess with a solid 2m of thinking typing this out.