百度&必应权4, 日IP8000. 查看详情
自助收录

844.比较含退格的字符串(解法一:暴力算法)

算法刷题2年前 (2023)更新 江南白衣
294 0 0
844.比较含退格的字符串(解法一:暴力算法)

844. 比较含退格的字符串
给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 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 = “b”
输出:false
解释:s 会变成 “c”,但 t 仍然是 “b”。
分析:本节不考虑任何算法,按常规思路直接硬写。
1、检查两个字符串中是否有#,如果有,移除#及其前一个字符
2、因为每次只能移除一个位置,所以要循环while (s.contains(“#”)),每次处理结束将原字符串替换为处理后的字符串
3、注意#出现在第一个字符时需要特殊处理,防止越界
4、了解StringBuilder.deleteCharAt(int index)StringBuilder.delete(int start, int end)的用法

package com.codernav.demo.leetcode.array.removeelement;

/**
 * 844. 比较含退格的字符串
 * 给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。
 * 注意:如果对空文本输入退格字符,文本继续为空。
 * 原文地址:https://www.codernav.com/2891.html
 * 更多算法详解:https://www.codernav.com
 */
public class Q_844 {
    public static void main(String[] args) {
        f("#ab#c#d", "ad#c");
    }

    private static boolean f(String s, String t) {
        // 如果字符串中包含#,对字符串进行处理
        while (s.contains("#")) {
            int pos = s.indexOf("#"); // #出现的位置,该方法只返回#出现的第一个位置
            StringBuilder sb = new StringBuilder(s);
            if (sb.indexOf("#") == 0) { // #在第一位单独处理,防止异常
                sb.deleteCharAt(0);
            } else {
                sb.delete(pos - 1, pos + 1); // #不在第一位,移除#和它的前一位置
            }
            s = sb.toString(); // 重新给字符串赋值
        }

        while (t.contains("#")) {
            int pos = t.indexOf("#");
            StringBuilder sb = new StringBuilder(t);
            if (sb.indexOf("#") == 0) {
                sb.deleteCharAt(0);
            } else {
                sb.delete(pos - 1, pos + 1);
            }
            t = sb.toString();
        }

        return s.equals(t);
    }
}

 

© 版权声明

相关文章

暂无评论

暂无评论...