844. 比较含退格的字符串

原题链接：

844. 比较含退格的字符串

https://leetcode.cn/problems/backspace-string-compare/description/

完成情况：

__844比较含退格的字符串

__844比较含退格的字符串__双指针

解题思路：

参考代码：

__844比较含退格的字符串

package 日常Java程序测试.代码随想录.数组;

public class __844比较含退格的字符串 {
	/**
	 *
	 * @param s
	 * @param t
	 * @return
	 */
	public boolean backspaceCompare(String s, String t) {
		//你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

		//给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
		//  #代表退格符
		//用两个指针，分别指向需要匹配的位置，就可以模拟退格？
		//还真可以，不过还得把String[]  转化成数组
		return myBuild(s).equals(myBuild(t));
	}

	/**
	 *
	 * @param str
	 * @return
	 */
	private String myBuild(String str) {
		StringBuilder retStringBuilder = new StringBuilder();
		int length = str.length();
		for (int i=0;i<length;i++){
			char ch = str.charAt(i);
			if (ch != '#'){
				retStringBuilder.append(ch);
			}else {
				if (retStringBuilder.length() > 0){
					retStringBuilder.deleteCharAt(retStringBuilder.length() - 1);
				}
			}
		}
		return retStringBuilder.toString();
	}
}

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

__844比较含退格的字符串__双指针

package 日常Java程序测试.代码随想录.数组;

public class __844比较含退格的字符串__双指针 {
	/**
	 *
	 * @param s
	 * @param t
	 * @return
	 */
	public boolean backspaceCompare(String s, String t) {
		int i = s.length() - 1,j = t.length() - 1;
		int skipS = 0,skipT = 0;

		while (i>=0 || j>= 0){
			while (i>=0){
				if (s.charAt(i) == '#'){
					skipS++;
					i--;
				} else if (skipS > 0) {
					skipS--;
					i--;
				}else {
					break;
				}
			}
			while (j >= 0){
				if (t.charAt(j) == '#'){
					skipT++;
					j--;
				} else if (skipT > 0) {
					skipT--;
					j--;
				}else {
					break;
				}
			}
			if (i>=0 && j>=0){
				if (s.charAt(i)!= t.charAt(j)){
					return false;
				}
			}else{
				if (i>=0 || j>=0){
					return false;
				}
			}
			i--;
			j--;
		}
		return true;
	}
}

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
48
49
50
51
52