leetcode10: rust

人に説明しようとする過程で理解が深まるってみんなが言ってた
何がわかってないのかがわからない赤ちゃんなので、マサカリブレードを投擲してくれる兄貴姉貴達を心待ちにしております

10 regular expression matching

文字列sとpを受け取り、sとpのパターンマッチングを行う
但し、pには２つのワイルドカード、'.'``'*'が含まれており、それぞれ
'.'は任意の文字とマッチする
'*'は直前の文字を任意の回数繰り返す

//　自力では解けなかった

note

回答を見ると再帰を用いる方法とdynamic programmingなる方法があった。再帰させる方は理解できたが、dpの方は訳がわからなかったので噛み砕いてみる

// dynamic programming
impl Solution {
   pub fn is_match(s: String, p: String,) -> bool {
      let mut dp = vec![vec![false; p.len() + 1]; s.len() + 1];
      dp[s.len()][p.len()] = true;

      for i in (0..=s.len()).rev() {
         for j in (0..p.len()).rev() {
            let first_match = i < s.len()
               && (p.chars().nth(j,) == s.chars().nth(i,)
	       || p.chars().nth(j,) == Some('.',));
            if j + 1 < p.len() && p.chars().nth(j + 1,) == Some('*',) {
               dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
            } else {
               dp[i][j] = first_match && dp[i + 1][j + 1];
            }
         }
      }
      dp[0][0]
   }
}

自分の解釈↓

dp[i][j]==trueの場合、これは

//擬似コード
is_match(&s[i..],&p[j..])==true

に対応、dp[i][j]==falseの場合、

is_match(&s[i..],&p[j..])==false

に対応している。そしてdp[i][j]==trueになる条件が２重forループの中に書かれている。具体的には

• sのi番目とpのj番目が同じ、またはpのj番目が.の場合first_match=true

• pのj番目が*の場合、*の繰り返す長さによって場合分け

  • *で一度も繰り返さない場合、*の部分はないものとして考えれられるので&p[j..]=p[j+2..]として考えても良い。つまりdp[i][j]にdp[i][j+2]の結果を代入できる。
  • *で少なくとも１回は繰り返しがある場合、s[i..=i]とp[j..=j]の比較はワイルドカードを含まない普通の文字どしの比較になる。なのでfirst_match=falseならば必ずdp[i][j]=false。first_match=trueならば、あとはそれに続く文字列がマッチすればいいのでdp[i][j]=dp[i+1][j]
    これらのどちらかがマッチしていれば良いので最終的にdp[i][j]=dp[i][j + 2] || first_match && dp[i + 1][j];

• pのj番目が*でない場合、first_match=trueかつ、それに続く文字列もマッチしてれば良いのでdp[i][j]=first_match && dp[i + 1][j + 1];

最後に、is_match(s,p)はdp[0][0]と同値なのでdp[0][0]を返す

こうして見るとdpと再帰って似てますね。あとこの問題から自然言語処理の闇の深さを垣間見た気がする