题解 | #正则表达式匹配#

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param str string字符串 
        * @param pattern string字符串 
        * @return bool布尔型
    */
    fun match(str: String,pattern: String): Boolean  {
        val dp = Array(str.length + 1) { 
            BooleanArray(pattern.length + 1) 
        }
        dp[0][0] = true
        for(i in 0..str.length) {
            for(j in 0..pattern.length) {
                if(i > 0 && j > 0 && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')) dp[i][j] = dp[i - 1][j - 1]
                else if(j > 0 && pattern[j - 1] == '*') {
                    if(j > 1) dp[i][j] = dp[i][j - 2]
                    if(i > 0 && j > 1 && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.')) dp[i][j] = dp[i][j] || dp[i - 1][j]
                }
            }
        }
        return dp[str.length][pattern.length]
    }
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param str string字符串 
        * @param pattern string字符串 
        * @return bool布尔型
    */
    fun match(str: String,pattern: String): Boolean  {
        //注意到其实我们的状态转移只与前一个数组有关（dp[i - 1][j - 1] 其中i - 1 表示使用前一个数组记录的值），因为我们维护两个数组，然后内部循环完之后交换数组的值就行了，这样可以节省空间
        val dp2 = BooleanArray(pattern.length + 1) 
        dp1[0] = true 
        dp2[0] = true
        for(i in 0..str.length) {
            for(j in 0..pattern.length) {
                if(i > 0 && j > 0 && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')) dp2[j] = dp1[j - 1]
                else if(j > 0 && pattern[j - 1] == '*') {
                    if(j > 1) dp2[j] = dp2[j - 2]
                    if(i > 0 && j > 1 && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.')) dp2[j] = dp2[j] || dp1[j]
                } else if(i > 0) dp2[j] = false
            }
            //最后交互值
            System.arraycopy(dp2, 0, dp1, 0, dp1.size)
        }
        return dp1[pattern.length]
    }
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param str string字符串 
        * @param pattern string字符串 
        * @return bool布尔型
    */
    fun match(str: String,pattern: String): Boolean  {
        val dp = BooleanArray(pattern.length + 1) 
        dp[0] = true
        //之前使用滚动数组来减少空间，但实际上这任然是浪费空间的，我们注意到我们实际上只使用了上一个数组的相同下标或前一个下标的值(dp[i - 1][j - 1] 表示前一个数组的当前下标的前一个值，dp[i - 1][j] 表示前一个数组相同下标的值)
        //因此我们可以用两个变量来记住这两个值即可
        var temp = true
        var prev = true
        for(i in 0..str.length) {
            prev = false
            for(j in 0..pattern.length) {
                //上一个数组相同下标对应的值
                temp = dp[j]
                if(i > 0 && j > 0 && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')) dp[j] = prev
                else if(j > 0 && pattern[j - 1] == '*') {
                    if(j > 1) dp[j] = dp[j - 2]
                    if(i > 0 && j > 1 && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.')) dp[j] = dp[j] || temp
                } else if(i > 0) dp[j] = false
                //上个数组的前一个下标对应的值
                prev = temp
            }
        }
        return dp[pattern.length]
    }
}