转载自Leet
Code
题目描述
给定 S 和 T
两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。
# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1： >输入：S = "ab#c", T = "ad#c"
>输出：true >解释：S 和 T 都会变成 “ac”。
示例 2： >输入：S = "ab##", T = "c#d#"
>输出：true >解释：S 和 T 都会变成 “”。
示例 3： >输入：S = "a##c", T = "#a#c"
>输出：true >解释：S 和 T 都会变成 “c”。
示例 4： >输入：S = "a#c", T = "b"
>输出：false >解释：S 会变成 “c”，但 T 仍然是
“b”。
提示： - 1 <= S.length <= 200 -
1 <= T.length <= 200 - S 和
T 只含有小写字母以及字符 '#'。
进阶： 你可以用 O(N) 的时间复杂度和 O(1)
的空间复杂度解决该问题吗？
我的代码
\(T(M,N) = O(max(M,N))\), \(S(M,N) = O(M+N)\)
{.line-numbers}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class MySolution844
{
public boolean backspaceCompare(String S, String T)
{
Stack<Character> stack1 = new Stack();
Stack<Character> stack2 = new Stack();
int i=0;
for (; i<S.length()&&i<T.length(); i++)
{
char ch1 = S.charAt(i);
if (ch1=='#'&&!stack1.isEmpty())
stack1.pop();
else if (Character.isAlphabetic(ch1))
stack1.push(ch1);
char ch2 = T.charAt(i);
if (ch2=='#'&&!stack2.isEmpty())
stack2.pop();
else if (Character.isAlphabetic(ch2))
stack2.push(ch2);
}
while(i<S.length())
{
char ch1 = S.charAt(i++);
if (ch1=='#'&&!stack1.isEmpty())
stack1.pop();
else if (Character.isAlphabetic(ch1))
stack1.push(ch1);
}
while(i<T.length())
{
char ch2 = T.charAt(i++);
if (ch2=='#'&&!stack2.isEmpty())
stack2.pop();
else if (Character.isAlphabetic(ch2))
stack2.push(ch2);
}
if (stack1.size()!=stack2.size()) return false;
while (!stack1.isEmpty()&&!stack2.isEmpty())
if (stack1.pop()!=stack2.pop()) return false;
return true;
}
}
|
方法：双指针
\(T(M,N) = O(M+N)\), \(S(N) = O(1)\)
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。
因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义skip表示当前待删除的字符的数量。
每次我们遍历到一个字符：
若该字符为退格符，则我们需要多删除一个普通字符，我们让skip加1；
若该字符为普通字符：
若skip为0，则说明当前字符不需要删去；
若skip不为0，则说明当前字符需要删去，我们让skip减1。
我们定义两个指针，分别指向两字符串的末尾。
每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，
然后将这两个字符进行比较。
重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
代码
{.line-numbers}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution496
{
Stack<Integer> stack;
HashMap<Integer, Integer> map;
public int[] nextGreaterElement(int[] nums1, int[] nums2)
{
Stack<Integer> stack;
HashMap<Integer, Integer> map;
public int[] nextGreaterElement(int[] nums1, int[] nums2)
{
stack = new Stack();
map = new HashMap();
for (int i=0; i<nums2.length; i++)
{
while (!stack.isEmpty()&&nums2[i]>stack.peek())
map.put(stack.pop(), nums2[i]);
stack.push(nums2[i]);
}
while (!stack.isEmpty())
map.put(stack.pop(), -1);
int []ans = new int[nums1.length];
for (int i=0; i<nums1.length; i++)
ans[i] = map.get(nums1[i]);
return ans;
}
}
|
