我最近在面试中被问到这个问题:
Given two strings s and t, return if they are equal when both are typed into empty text editors. # means a backspace character.
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) 空间复杂度内解决它吗?
注意:我们也可以有多个退格字符。
最佳答案
为了实现 O(1)
空间复杂度,使用两个指针并从字符串的末尾开始:
public static boolean sol(String s, String t) {
int i = s.length() - 1;
int j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = consume(s, i);
j = consume(t, j);
if (i >= 0 && j >= 0 && s.charAt(i) == t.charAt(j)) {
i--;
j--;
} else {
return i == -1 && j == -1;
}
}
return true;
}
主要思想是维护#
计数器:如果字符是#
,则递增cnt
,否则递减。如果 cnt > 0
和 s.charAt(pos) != '#'
- 跳过字符(递减位置):
private static int consume(String s, int pos) {
int cnt = 0;
while (pos >= 0 && (s.charAt(pos) == '#' || cnt > 0)) {
cnt += (s.charAt(pos) == '#') ? +1 : -1;
pos--;
}
return pos;
}
时间复杂度:O(n)
。
关于java - 用于检查带退格的字符串是否相等的节省空间的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56615004/