用于检查带退格的字符串是否相等的节省空间算法?
2022-09-04 02:58:58
我最近在一次采访中被问到这个问题:
给定两个字符串 s 和 t,当两者都键入到空文本编辑器中时,如果它们相等,则返回。# 表示退格字符。
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
我想出了以下解决方案,但它不节省空间:
public static boolean sol(String s, String t) {
return helper(s).equals(helper(t));
}
public static String helper(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c != '#')
stack.push(c);
else if (!stack.empty())
stack.pop();
}
return String.valueOf(stack);
}
我想看看是否有任何更好的方法来解决这个问题,它不使用堆栈。我的意思是,我们可以在O(1)空间复杂度中解决它吗?
注意:我们也可以有多个退格字符。