925. 长按键入
1.题目:
你的朋友正在使用键盘输入他的名字 name
。偶尔,在键入字符 c
时,按键可能会被长按,而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed
。如果它对应的可能是你的朋友的名字(其中一些字符可能被长按),那么就返回 True
。
示例 1:
输入:name = "alex", typed = "aaleex" 输出:true 解释:'alex' 中的 'a' 和 'e' 被长按。
示例 2:
输入:name = "saeed", typed = "ssaaedd" 输出:false 解释:'e' 一定需要被键入两次,但在 typed 的输出中不是这样。
2.思路:
双指针
使用两个下标 i,ji,ji,j 追踪 name 和 typed的位置。
当 name[i]=typed[j]时,说明两个字符串存在一对匹配的字符,此时将i,j 都加 1。
否则,如果 typed[j]=typed[j−1],说明存在一次长按键入,此时只将 j 加 1。
最后,如果 i=name.length,说明 name的每个字符都被「匹配」了。
3.代码:
class Solution {
public boolean isLongPressedName(String name, String typed) {
if(typed.length()<name.length()){
return false;
}
int n=0,t=0;
while(t<typed.length()){
if(n<name.length() && name.charAt(n)==typed.charAt(t)){
t++;
n++;
}else{
if(t>0 && typed.charAt(t)==typed.charAt(t-1)){
t++;
}else{
return false;
}
}
}
return n==name.length();
}
}
844. 比较含退格的字符串
1.题目:
给定 s
和 t
两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true
。#
代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 1:
输入:s = "ab#c", t = "ad#c" 输出:true 解释:s 和 t 都会变成 "ac"。
示例 2:
输入:s = "ab##", t = "c#d#" 输出:true 解释:s 和 t 都会变成 ""。
示例 3:文章来源:https://www.toymoban.com/news/detail-638763.html
输入:s = "a#c", t = "b" 输出:false 解释:s 会变成 "c",但 t 仍然是 "b"。
2.思路:
双指针--从后向前统计两个字符串的# 并模拟删除操作(长度减一)得到没有退格符的字符串,从后向前统计字符串的每一位是否相等,相等返回true。文章来源地址https://www.toymoban.com/news/detail-638763.html
3.代码:
class Solution {
public boolean backspaceCompare(String s, String t) {
//双指针
int lengthS=s.length()-1,lengthT=t.length()-1;
int backSpaceS=0,backSpaceT=0;
while(lengthS>=0 || lengthT>=0){
while(lengthS>=0){
if(s.charAt(lengthS)=='#'){
backSpaceS++;
lengthS--;
}else if(backSpaceS>0){
backSpaceS--;
lengthS--;
}else{
break;
}
}
while(lengthT>=0){
if(t.charAt(lengthT)=='#'){
backSpaceT++;
lengthT--;
}else if(backSpaceT>0){
backSpaceT--;
lengthT--;
}else{
break;
}
}
if(lengthS>=0 && lengthT>=0){
if(s.charAt(lengthS)!=t.charAt(lengthT)){
return false;
}
}else{
if(lengthS>=0 || lengthT>=0){
return false;
}
}
lengthS--;
lengthT--;
}
return true;
}
}
到了这里,关于Practices8(双指针)|925. 长按键入、844. 比较含退格的字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!