844. Compare strings with backspace

1、 Title Description

 2、 title

Double pointer traversal method

Thinking analysis ：

• 1、 Prepare two pointers i, j Point to respectively S,T  Last character of , Prepare two more variables skipS,skipT To store... Separately S,T  In the string # Number .
• 2、 Go back and forth S, There are three situations , As shown below ：
• 2.1 If the current character is #, be skipS  Self increasing 1;
• 2.2 If the current character is not #, And skipS  Not for 0, be skipS  Self reduction 1;
• 2.3 If the current character is not #, And skipS  by 0, It means that the current character will not be eliminated , We can use it with T Compare the current character in the .
• If the comparison process occurs S, TT The current character does not match , Then the traversal ends , return false, if S,T  All traversal ends , And can match one by one , Then return to true.

class Solution {
    public boolean backspaceCompare(String s, String t) {
         int i = s.length()-1; 
         int j = t.length()-1;
         int skipS = 0; int skipT = 0;
         // Only i perhaps j There is one  >= 0, Check the space , Data comparison 
         //  remarks ： Extremely important , Don't write it   while(i > 0 || j > 0)
         while(i >= 0 || j >= 0){
              // Yes s String to check , All spaces are currently involved  ‘#’  Uniform backspace 
              while( i >= 0 ){
                  if(s.charAt(i)=='#'){
                      i--;
                      skipS++;
                  }else if(skipS > 0){
                      i--;
                      skipS--;
                  }else{
                      break;
                  }
              }

              // Yes t String to check , All spaces are currently involved  ‘#’  Uniform backspace 
              while( j >= 0){
                 if(t.charAt(j)=='#'){
                     j--;
                     skipT++;
                 }else if(skipT > 0){
                     j--;
                     skipT--;
                 }else{
                     break;
                 }
              }

           if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) return false;
            } else if (i >= 0 || j >= 0) {
                //  One of them has traversed the whole string ,  But the other party didn't traverse the whole string ,  Go straight back to false
                return false;
            }
            i--;
            j--;
         }

        return true;
    }
}

Complexity analysis

Time complexity ：O(N+M), among N  and M  They are strings S  and T The length of . We need to traverse both strings once .

Spatial complexity ：O(1). For each string , We just need to define a pointer and a counter .

remarks ： This question is 【JAVA】 Implementation code （ The above code ）, There are many details , When compiling the self-test , Often case Compile exception , For example, the notes say ：

1、  while(i >= 0 || j >= 0)   // Only i perhaps j There is one >= 0, Check the space , Data comparison
        remarks ： Extremely important , Don't write it  while ( i > 0 ||  j > 0 )

2、 while The last check in ,

        if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) return false;
        } else if (i >= 0 || j >= 0) {
                // One of them has traversed the whole string , But the other party didn't traverse the whole string , Go straight back to false
                return false;
       }

Specifically for the following case Of , When submitting the code , Often fail to measure ！

/**
 "bbbextm"
 "bbb#extm"

  Output ：true
  Expected results ：false
 */