【LeetCode算法题】-Backspace String Compare

一、看题和准备

今天介绍的是LeetCode算法题中Easy级别的第197题(顺位题号是844)。给定两个字符串S和T,如果两个字符串都输入到空文本编辑器中并且相等,则返回true。 #表示退格符。例如:


输入:S =“ab#c”,T =“ad#c”

输出:true

说明:S和T都变为“ac”。


输入:S =“ab ##”,T =“c#d#”

输出:true

说明:S和T都变为“”。


输入:S =“a ## c”,T =“#a#c”

输出:true

说明:S和T都变为“c”。


输入:S =“a#c”,T =“b”

输出:false

说明:S变为“c”而T变为“b”。


注意

  • 1 <= S.length <= 200

  • 1 <= T.length <= 200

  • S和T仅包含小写字母和“#”字符。

跟进:能在O(N)时间和O(1)空间解决它吗?


本次解题使用的开发工具是InteIIiJ IDEA,jdk使用的版本是1.8,环境是win10 64位系统,使用Java语言编写和测试。

二、第一种解法

通过栈的用法,先转换成新的字符串,只不过是使用栈来实现,借助其先进后厨的特性。

先遍历字符串中的字符,如果当前字符不是#号,就入栈;如果遇到#号,就需要回退一个字符,只要将栈顶的元素出栈即可,但是先判断栈中是否包含元素。。

public static  boolean Compare(String S,String T){
        return build(S).equals(build(T));
    }
    public  static  String build(String str){
        Stack<Character> stack = new Stack<>();
        for (char ch:str.toCharArray()
             ) {
            if (ch!='#'){
                stack.push(ch);
            }else if(!stack.isEmpty()){
                stack.pop();
            }
        }
        return String.valueOf(stack);
    }

三、第二种解法

从后向前遍历字符串中的字符,统计遇到的#号个数,直到遇到字母为止,然后累加字符,变成一个新的字符串,另外的同理。

 public static boolean backspaceCompare(String S,String T){
        return rebuild(S).equals(rebuild(T));
    }
    public static String rebuild(String str){
        String newStr = "";
        int count = 0;
        for (int i=str.length()-1;i>=0;i--) {
            char ch = str.charAt(i);
            if(ch=='#'){
                count++;
            }else {
                if(count>0){
                    count--;
                }else{
                    newStr += ch;
                }
            }
        }
        return newStr;
    }

四、第三种解法

  public  static boolean backspaceCompare3(String S,String T){
        int i = S.length()-1,j=T.length()-1;
        while(S.length()-1>=0||T.length()-1>=0){
            i = helper(S,i);
            j = helper(T,j);
            //判断当前的i和j对应的字符串是否相等
            if(i>=0 && j>=0 && S.charAt(i)!=T.charAt(j)){
                return false;
            }
            //如果i或者j小于0时,判断两者是否同时小于0
            if(i<0||j<0){
                return i==j;
            }
            i--;
            j--;
        }
        return true;
    }
    public static int helper(String str,int index){
        int  count = 0;
        while(index>0){
            if(str.charAt(index)=='#'){
                count++;
                index--;
            }else if(count >0){
                count--;
                index--;
            } else {
                break;
            }
        }
        return index;
    }

 

全部评论

相关推荐

程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
牛客383479252号:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务