【アルゴリズム】Reglar Expression Match正則マッチング

【アルゴリズム】Reglar Expression Match正則マッチング

テーマ

解く発想

コード実現

テーマ
Gven an input string(s)and a pattern(p)、implement reglar expression matching with support for'.and'*'
‘Match’any single character.‘＊’Match zeror more of the preceding element.The matching shoruld cover the ntire input string.
ノート:
s could be empty and contains only lowercase letters a-z.p could be empy and contains only lowercase letters a-z,and characters like.or*.Example 1:
Input:

s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

文字列sとpを指定します.表式pは「.」と「*」を含んでいます.

「.」は任意の文字にマッチすることができます.

「*」は、0から無限の「*」の前のビットの文字にマッチすることができます.例えば、「a*」は0から無限の「a」にマッチすることができます.

文字はa~z

です.

sおよびpは、空の文字列

でありうる.
sとpが合っているかどうかを判断します.
問題を解く構想
ダイナミック・プランニング(dynamic programming)方法を用いて、dp[i][j]はs前のi文字がp前のj文字と一致するかどうか、デフォルト値はfalseです.dp[i][j]を見つけた表現は以下の通りです.

p[j-1]が*ではなく、s[i-1]がp[j-1]と一致する場合(文字と同じp[j-1]が.)、dp[i]=dp[i-1]、[j-1]

p[j-1]が*であり、*がマッチングしていない場合、dp[i]=dp[i]、[j-2]

p[j-1]が*であり、*がマッチングすると、dp[i]=[j]=dp[i-1]、[j]&(s[i-1]==p[j-2]|p[j-2]==“.’)

ps:ここi jは長さを表していますので、i番目を文字とする場合はs[i-1]を使います.
コードの実装
Runtime:20 msメモリ:20.7 MB

func isMatch(_ s: String, _ p: String) -> Bool {
        //  String     Array ，      
        let s = Array(s),p = Array(p)
        //m n   s p    
        let m = s.count, n = p.count
        //dp[i][j]    s   i      p   j        ，     false
        var dp = Array(repeating: Array(repeating: false, count: n+1), count: m+1)
        // s p         ，   dp[0][0] = true
        dp[0][0] = true
        //   p    ，    s       true，       false
        //         dp[0][0] = true ，   p     1     n
        //   n   0        ，    
        if n > 0 {
            //   s    ，  0   m
            for i in 0 ... m {
                //    p    ，
                for j in 1 ... n {
                    //          
                    //         i j       ，     i         s[i-1]
                    //1.  p[j - 1]    *，  s[i - 1]   p[j - 1]   （        p[j-1]   . ） ，dp[i][j] = dp[i - 1][j - 1]
                    //2.  p[j - 1]   *，  *        ，dp[i][j] = dp[i][j - 2]
                    //3.  p[j - 1]   *，  *        ，dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')
                    
                    //   j     2  ，  p[j-1]   *  ，   *    
                    if (j > 1 && p[j-1] == "*") {
                        //   *   ，       2     3     ，          ，     
                        dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i-1]  == p[j-2] || p[j-2] == ".") && dp[i - 1][j])
                    }else{
                        //        * ，            1
                        dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i-1] == p[j-1] || p[j-1] == ".")
                    }
                }
            }
        }
        //    
        return dp[m][n];
    }

コードアドレス:https://github.com/sinianshou/EGSwiftLearning