arrays - 用恒定空间统一目录路径的算法

Question

我正在经历一些编码练习，并且遇到了一个问题来实现统一目录路径的功能。

例子：

• 输入：/dir1/dir2/../dir3/file.txt

• 输出：/dir1/dir3/file.txt

我们可以使用堆栈以 O(n) 的时间/空间复杂度来解决这个问题。但是我们不想使用额外的空间。

我们如何以 O(1) 的空间复杂度解决这个问题？我正在为就地解决方案而苦苦挣扎。

Answer 1

我认为，没有写它，你可以用一个额外的指针来购买。因为最后，您主要是在做移位，您可以简单地让一个指针代表您当前的位置扫描字符串，然后将另一个指针作为字符串中的目标位置。关键是您在进行过程中积极地使用字符串。

例如：

/dir1/dir2/../dir3/file.txt

当您点击 时..，您的“当前指针”保持在/of 上/dir3。

..然后，您使用目标指针从up 到/of向后扫描/dir2。

完成目标指针后，将字符串中的所有内容从当前指针 ( /of /dir3) 向上移动，同时调整当前指针。

然后你冲洗并重复，直到你完成。/./路径也会发生同样的事情。只需类似地消耗它。

您可以在中间使用目标指针来记录当前标记的开始，但基本上您只需在字符串移动到位时进行一堆上下扫描。

这只是一个猜测，有 2m 的时间想把它打出来。