データ構造とアルゴリズムの比較バックスペースを含む文字列!

[[441739]]

バックスペースで文字列を比較する

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/backspace-string-compare

2 つの文字列 S と T がそれぞれ空のテキストエディターに入力された場合、2 つの文字列が等しいかどうかを判定し、結果を返します。 # はバックスペース文字を表します。

注意: 空のテキストにバックスペース文字を入力すると、テキストは空のままになります。

例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 = "#a#c"
出力: true
説明: S と T は両方とも「c」になります。

例4:

入力: S = "a#c"、T = "b"
出力: false
説明: S は「c」になりますが、T は「b」のままです。

アイデア

この記事では、空間計算量を伴うスタックシミュレーション方式と空間計算量を伴うダブルポインター方式について説明します。

通常の方法（スタックの考え方を使用）

この問題では、明らかにスタックを使用する必要があります。この種のマッチング (消去) 問題も、スタックが得意とする分野です。私と一緒に学習する学生は、スタックとキューにおけるマッチング問題がスタックの強みであることを理解する必要があります。同様のことを行うためにスタックを使用することについては、すでに一度触れました。

したがって、この問題では、スタックの考え方を実際に使用できますが、最後に比較するときにスタック内の要素も比較する必要があるため、スタックを使用する必要はありません。これは少し面倒です。

ここでは、文字列をそのままスタックとして使用し、最後に追加とポップを行い、文字列には対応するインターフェースがあります。最後に比較するときは、2 つの文字列を比較するだけで済み、スタック内の要素を比較するよりも便利です。

コードは次のとおりです。

クラスソリューション{
公共：
    bool backspaceCompare(文字列S、文字列T) {
        string s; // スタックとして使用
        string t; // スタックとして使用
( int i = 0; i < S.size ( ); i++) {
            S[i] != '#'の場合、 s += S[i];
それ以外の場合 (!s.empty()) {
                s.pop_back(); 
 
        }
 ( int i = 0; i < T.size ( ) ); i++) {
            T[i] != '#'の場合、t += T[i];
それ以外の場合は (!t.empty()) {
                t.pop_back();
            }
        }
        (s == t)の場合、戻り値  true ; // 2つの文字列が等しいかどうかを直接比較する方が、スタックを使用するよりもはるかに便利です
戻る 間違い;
    }
 };

時間計算量: nはSの長さ、mはTの長さであり、時間計算量とも言える。

空間計算量: もちろん、上記のコードでは、処理 S と処理 T の繰り返しロジックがあることがわかります。この共通ロジックを抽出して、コードを次のように簡略化できます。

クラスソリューション{
プライベート：
文字列 getString(const string& S) {
    文字列 s;
 ( int i = 0; i < S.size ( ); i++) {
        S[i] != '#'の場合、 s += S[i];
それ以外の場合 (!s.empty()) {
            s.pop_back();
        }
    }
 sを返します。
 }
公共：
    bool backspaceCompare(文字列S、文字列T) {
 getString(S) == getString(T)を返します。
    }
 };

パフォーマンスは依然として次のとおりです。

時間の計算量:
空間の複雑さ:

最適化方法（後ろから前へのダブルポインタ）

もちろん、この問題を解決するために使用する空間計算量もあります。

同時に、S と T を後ろから前へトラバースし (i は最初は S の末尾にあり、j は最初は T の末尾にあります)、# の数を記録し、消去操作をシミュレートし、# が使い果たされた場合は、S[i] と S[j] の比較を開始します。

アニメーションは次のとおりです。

S[i]とS[j]が同じでない場合は、falseが返されます。一方のポインタ（iまたはj）が最初に文字列の先頭に到達した場合も、falseが返されます。

コードは次のとおりです。

クラスソリューション{
公共：
    bool backspaceCompare(文字列S、文字列T) {
 int sSkipNum = 0; // Sの数を記録する
int tSkipNum = 0; // Tの数を記録する
int i = S.size ( ) - 1;
 int j = T.size ( ) - 1;
        一方（1）{
            while (i >= 0) { // 後ろから前へ、S# を削除します
                S[i] == '#'の場合、 sSkipNum++;
それ以外{
                    sSkipNum > 0 の場合、 sSkipNum --;  
そうでなければ中断します。
                }
                私  - ;  
            }
            while (j >= 0) { // 後ろから前に向かってTを削除します #
                T[j] == '#'の場合、tSkipNum++;
それ以外{
                    tSkipNum > 0 の場合、tSkipNum --;  
そうでなければ中断します。
                }
                j --;  
            }
            // 後半の半分# は削除され、S[i] != T[j] と比較されます
            if (i < 0 || j < 0) break; // S または T がトラバーサルの終了に到達しました
            (S[i] != T[j]) の場合、戻り値 間違い;
            私は--;j--;  
        }
        // SとTが同時に走査されることを示します
        (i == -1 && j == -1)の場合、戻り値 真実;
戻る 間違い;
    }
 };

時間の計算量:
空間の複雑さ:

その他の言語

ジャワ:

 // 通常のメソッド（スタックの考え方を使用）
クラスソリューション{
パブリックブールバックスペース比較(文字列s、文字列t) {
        StringBuilder ssb = new StringBuilder(); // スタックをシミュレートする
        StringBuilder tsb = new StringBuilder(); // スタックをシミュレートする
        // 2つの文字列を別々に処理する
( char c : s.toCharArray())の場合{
            （c != '#' ）の場合{
                ssb.append(c); // スタッキングをシミュレートする
            } else if (ssb.length() > 0){ // スタックをポップするにはスタックが空でない必要がある
                ssb.deleteCharAt(ssb.length() - 1); // スタックのポップをシミュレートする
            }
        }
 ( char c : t.toCharArray())の場合{
            （c != '#' ）の場合{
                tsb.append(c); // スタッキングをシミュレートする
            } else if (tsb.length() > 0){ // スタックをポップするにはスタックが空でない必要がある
                tsb.deleteCharAt(tsb.length() - 1); // スタックのポップをシミュレートする
            }
        }
 ssb.toString().equals(tsb.toString());を返します。
    }
 }

パイソン

クラスソリューション: 
 
    get_string(self, s: str) を定義します。
        bz = []
 i が範囲(len(s))内にある場合:
            c = s[i]
            c != '#'の場合:
                bz.append(c) # スタッキングをシミュレートする
            elif len(bz) > 0: # スタックをポップするにはスタックが空でない必要があります
                bz.pop() # スタックのポップをシミュレートする
str(bz)を返す
 
    def backspaceCompare(self, s: str, t: str) -> bool:
 self.get_string(s) == self.get_string(t)を返します。
        合格

行く

getString関数(文字列)文字列{
 bz := []ルーン{}
 _の場合、c := 範囲 s {
  c != '#'の場合{
   bz = append(bz, c); // スタッキングをシミュレートする
  } else if len(bz) > 0 { // スタックをポップするにはスタックが空でない必要がある
   bz = bz[:len(bz)-1] // スタックポップをシミュレートする
  }
 }
文字列を返す(bz)
 } 
 
 func backspaceCompare(s 文字列, t 文字列) bool {
 getString(s) == getString(t)を返します。
 }

JavaScript

 //デュアルスタック
 
 var backspaceCompare =関数(s, t) { 
 
 const arrS = [], arrT = []; // スタックとして使用される配列
 
 (let charの場合 の）{ 
 
 char === '#' ? arrS.pop() : arrS.push( char ); 
 
 } 
 
 (let charの場合  t ){の
 
 char === '#' ? arrT.pop() : arrT.push( char ); 
 
 } 
 
 return arrS.join ( '' ) === arrT.join ( ' ' ) ; // 2つの文字列が等しいかどうかを比較する
 
 }; 
 
 //デュアルスタックの簡素化
 
 var backspaceCompare =関数(s, t) { 
 
定数getString = s => { 
 
 arrS = [] とします。 
 
 (let charの場合 の）{ 
 
 char === '#' ? arrS.pop() : arrS.push( char ); 
 
 } 
 
 arrS.join ( '' )を返します。 
 
 } 
 
 getString(s) === getString(t) を返します。 
 
 }; 
 
 //ダブルポインタ
 
 var backspaceCompare =関数(s, t) { 
 
 let sSkipNum = 0; // sの数を記録する
 
 let tSkipNum = 0; // tの数を記録する
 
 i = s.length - 1、j = t.length - 1とします。 
 
 while( true ) { 
 
 while(i >= 0){ // 後ろから前へ、s# を削除します
 
 s[i] === '#'の場合、 sSkipNum++; 
 
それ以外{ 
 
 sSkipNum > 0 の場合、 sSkipNum --;   
 
そうでなければ中断します。 
 
 } 
 
私  - ;   
 
 } 
 
 while (j >= 0) { // 後ろから前へ、t# を削除します。 
 
 t[j] === '#'の場合、tSkipNum++; 
 
それ以外{ 
 
 tSkipNum > 0 の場合、tSkipNum --;   
 
そうでなければ中断します。 
 
 } 
 
 j --;   
 
 } 
 
 // 後半の半分# は削除され、s[i] != t[j] と比較されます
 
 if (i < 0 || j < 0) break; // s または t が走査の終わりに到達しました
 
 s[i] !== t[j] の場合、戻り値 間違い; 
 
私は--;j--;   
 
 } 
 
 // s と t が同時に走査されることを示します
 
 (i == -1 && j == -1)の場合、戻り値 真実; 
 
戻る 間違い; 
 
 };