844 - 比较含退格的字符串 + 925 - 长键输入 - Java

比较含退格的字符串

给定 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或者S来说，如果遇到退格字符#，就需要将它前面的一个字符退格（删除）。最后判断剩下的字符串T和字符串S是否一致，如果一致返回true，否则返回false。

由于涉及到可能的删除操作，我们可以使用Stack来存储字符串中可能出现的所有字符，最后判断Stack表示的字符串是否一致即可。

class Solution { public boolean backspaceCompare(String S, String T) { String r1 = judge(S); String r2 = judge(T); return r1.equals(r2) ? true : false; } public String judge(String str){ if(str == null){ return new String(); } Stack<Character> stack = new Stack<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if(c != '#'){ stack.push(c); } else if(c == '#' && !stack.isEmpty()){ stack.pop(); } else { continue; } } return stack.toString(); } }

---

---

长键输入

你的朋友正在使用键盘输入他的名字name。偶尔，在键入字符c 时，按键可能会被长按，而字符可能被输入1次或多次。你将会检查键盘输入的字符typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回True。

示例 1：

输入：name = "alex", typed = "aaleex" 输出：true 解释：'alex' 中的 'a' 和 'e' 被长按。

示例 2：

输入：name = "saeed", typed = "ssaaedd" 输出：false 解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

示例 3：

输入：name = "leelee", typed = "lleeelee" 输出：true

示例 4：

输入：name = "laiden", typed = "laiden" 输出：true 解释：长按名字中的字符并不是必要的。

提示：

$name.length<=1000$$typed.length<=1000$name 和 typed 的字符都是小写字母。

---

对于给定的字符串typed中的字符有两种合法的形式：

一种是和name相对位置的字符相同另一种属于长键字符，即当前位置的字符和它前一个位置的字符相同

题目要求在考虑长键输入的前提下，name和typed表示的字符串是否相同。因此，我们可以使用双指针法来遍历两个字符串。设定left和right分别指向name和typed的起始位置：

如果此时left还未到达name的末尾，而且right指向的字符和left指向的字符相同，则两者都往后移动一次如果right不位于起始位置，而且right和right - 1指向的字符相同，这就输入长键字符，right往后移动如果不满足上面的两种情况，那么typed必然不能构成name，直接返回false

最后只需要判断left是否成功的到达字符串末尾。

class Solution { public boolean isLongPressedName(String name, String typed) { if(name == null || typed == null){ return false; } int left = 0; int right = 0; while(right < typed.length()){ if(left < name.length() && name.charAt(left) == typed.charAt(right)){ left++; right++; } else if(right > 0 && typed.charAt(right) == typed.charAt(right - 1)){ right++; } else{ return false; } } return left == name.length() ? true : false; } }