Compares strings that contain backspace

Given two strings S and T, when each is entered into a blank text editor, determine if the two are equal and return the result. # stands for backspace character.

Note: If you enter a backspace character for empty text, the text remains empty.

Example 1:

Enter: S ="ab#c", T = "ad#c"Output:trueExplanation: both S and T become "ac".Copy the code

Example 2:

Enter: S ="ab##", T = "c#d#"Output:trueExplanation: both S and T become "".Copy the code

Example 3:

Enter: S ="a##c", T = "#a#c"Output:trueExplanation: both S and T become "C".Copy the code

Example 4:

Enter: S ="a#c", T = "b"Output:falseExplanation: S becomes a "C", but T is still a "B".Copy the code

Tip:

  • 1 < = S . l e n g t h < = 200 1 <= S.length <= 200 1<=S.length<=200
  • 1 < = T . l e n g t h < = 200 1 <= T.length <= 200 1<=T.length<=200
  • S and T contain only lowercase letters and charactersThe '#'.

Advanced: Can you solve this problem with O(N) time complexity and O(1) space complexity?

For the input string T or S, if you encounter the backspace character #, you need to backspace the character before it. Finally, determine whether the remaining string T and string S are consistent, returning true if they are, false otherwise.

Since possible deletion operations are involved, we can use Stack to store all possible characters in the string, and finally determine whether the string represented by Stack is consistent.

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 ! =The '#'){
                stack.push(c);
            } else if(c == The '#' && !stack.isEmpty()){
                stack.pop();
            } else {
                continue; }}returnstack.toString(); }}Copy the code

Long key input

Your friend is typing his name on the keyboard. Occasionally, the key may be long pressed when typing the character C, and the character may be typed one or more times. You will check the typed character on the keyboard. Return True if it might correspond to your friend’s name (some of which might be long pressed).

Example 1:

Enter: name ="alex", typed = "aaleex"Output:trueExplanation:'alex'In the'a' 和 'e'By long press.Copy the code

Example 2:

Enter: name ="saeed", typed = "ssaaedd"Output:falseExplanation:'e'It always needs to be typed twice, but in typed output this is not the case.Copy the code

Example 3:

Enter: name ="leelee", typed = "lleeelee"Output:true
Copy the code

Example 4:

Enter: name ="laiden", typed = "laiden"Output:trueExplanation: Long pressing characters in names is not necessary.Copy the code

Tip:

  • n a m e . l e n g t h < = 1000 name.length <= 1000 name.length<=1000
  • t y p e d . l e n g t h < = 1000 typed.length <= 1000 typed.length<=1000
  • The characters of name and typed are lowercase letters.

There are two valid forms for characters typed in a given string:

  • One kind is andnameThe characters in relative positions are the same
  • The other is a long-key character in which the character at the current position is the same as the character at the position before it

Are name and typed the same string with long keys taken into account? Therefore, we can use the double-pointer method to iterate over two strings. Set left and right to the starting position of name and typed respectively:

  • If at this timeleftHas not yet reachednameAt the end of, andrightThe character and point toleftIf they point to the same character, both move back once
  • ifrightNot in the starting position, andrightandright - 1It points to the same character, so long key character,rightMove back
  • If the above two conditions are not met, thentypedMust not constitutename, return directlyfalse

In the end, you just need to check whether left has successfully reached the end of the string.

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; }}Copy the code