题解 | #字符串通配符#

字符串通配符

http://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036

动态规划方法解字符串通配符问题

理解题目：

字符串为str（长度s_len），匹配模式为pattern（长度p_len）。要使得两者匹配，即需要完成匹配函数match(*str, *pattern)。

简写match函数为：m，描述两者完整长度匹配的表示为：m(s_len, p_len) 由数学归纳法，描述str前i个字符匹配 pattern前j个长度的表示为：m(i, j)

推理转换：

可以将m(i, j)以坐标轴形式表示，则m(s_len, p_len)为最远的坐标点。问题转换为，是否能找到一条用true连成的，通往最终m(s_len, p_len)坐标的连线。 alt 为了找到这条连线，可以有两种做法：

1、先找到第一个T，沿着第一个T的附近，找到另一个可以连接的T，然后依次类推到任意坐标轴长度耗尽，看是否能走到m(s_len， p_len) 【递归】
2、从小到大，遍历所有坐标，并将m(i, j)的结果（T 或 F）都算出来，最后就能算出m(s_len, p_len) 【迭代】

算法表示：

以上的提到的两种做法都是动态规划的方法，其中【迭代】方法可以让中间状态更清晰，更容易理解，以下仅介绍实现【迭代】方法

根据迭代方法的描述，要算出最终坐标的m(s_len，p_len)，则需要先算出所有坐标m(i, j)。因此需要找到以下三个关键要素：

1、状态转移方程：即m(i, j)与其之前的坐标关系，例如m(i-1, j-1)，m(i-1, j)，m(i, j-1)
2、初始状态值：即m(0, 0)
3、边界状态值：即m(1, 0) 到 m(s_len, 0)，以及m(0, 1) 到 m(0, p_len)

算法套用：

创建动态规划矩阵dp[s_len+1][p_len+1]用以存放m(i, j)的结果因为要考虑初始和边界状态值（实际意义为空字符串和空模式的匹配结果），因此dp矩阵两个维度都需要+1

以下来找上面提到的三个关键要素：

1、状态转移方程：根据题目条件，我们区分三种情况讨论状态转移方程，令s_ch = str[i-1]，p_ch = pattern[j-1]，则

//如果当前，第i字符和第j个模式，不区分大小写的匹配成功
//则当前匹配结果，等同于前i-1个字符和前j-1个模式的匹配结果
if(strncasecmp(&p_ch, &s_ch, 1) == 0)
	dp[i][j] = dp[i-1][j-1];

//如果当前，第j个模式为?，且第i个字符为非符号字符
//则当前匹配结果，等同于前i-1个字符和前j-1个模式的匹配结果
if(p_ch == '?' && s_ch_not_symbol[i])
	dp[i][j] = dp[i-1][j-1];

//如果当前，第j个模式为*，且第i个字符为非符号字符，一下三种*的匹配方法均可
//令*匹配0个字符，则当前i个字符需要匹配*以前的j-1个模式，即dp[i][j] = dp[i][j-1]
//令*匹配1个字符（等同?），则dp[i][j] = dp[i-1][j-1]
//令*匹配任意多字符，则只要前i-1个字符与当前j个模式匹配，即dp[i][j] = dp[i-1][j]
if(p_ch == '*' && s_ch_not_symbol[i])
	dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j];

2、初始状态值：因为空字符串与空模式，结果恒成功：

dp[0][0] = true

3、边界状态值：因为非空字符串匹配空模式，结果恒失败：

for(int i = 1; i <= s_len; i++)
	dp[i][0] = false;

因为空字符串匹配非空模式，只有当非空模式为全"*"（只有"*"能匹配0个字符），才能匹配成功：

for(int j = 1; j <= p_len; j++)
	dp[0][j] = dp[0][j-1] && (p_ch == '*');

最终实现：

#include <iostream>
#include <string>
#include <string.h>

using namespace std;

bool char_not_symbol(char ch)
{
    return (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

bool iteration_match(string pattern, string str)
{
    int s_len = str.size();
    int p_len = pattern.size();
    //dp[i][j] 记录前i个字符串[0,i-1]与前j个模式[0,j-1]的匹配结果
    bool dp[s_len+1][p_len+1];
    //记录str中的每个字符是否非符号
    bool s_ch_not_symbol[s_len+1];
    
    memset(dp, 0, sizeof(dp));
    memset(s_ch_not_symbol, 0, sizeof(s_ch_not_symbol));
    
    //空字符串 匹配 空模式 结果恒为true
    dp[0][0] = true;
    //非空字符串 匹配 空模式 结果恒为false
//     for(int i = 1; i <= s_len; i++)
//         dp[i][0] = false;
    
    //空字符非符号字符
    s_ch_not_symbol[0] = true;
    for(int j = 1; j <= p_len; j++)
    {
        //当前判断的模式
        char p_ch = pattern[j-1];
        //空字符串 匹配 非空模式，只有前j个模式全为*才能匹配为true
        dp[0][j] = dp[0][j-1] && (p_ch == '*');
        for(int i = 1; i <= s_len; i++)
        {
            //当前判断的字符
            char s_ch = str[i-1];
            
            if(j == 1) //初始化非符号字符判断记录
                s_ch_not_symbol[i] = char_not_symbol(s_ch);
            
            //前i个字符串 匹配 前j个模式  
            if(p_ch == '*' && s_ch_not_symbol[i])  //当前模式为*，匹配0个即[i][j-1]，匹配1个即[i-1][j-1]，匹配多个即[i-1][j]，均可
                dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j];
            else if((p_ch == '?' && s_ch_not_symbol[i]) || strncasecmp(&p_ch, &s_ch, 1) == 0)  //当前模式为?或者当前字符，则只要前i个字符串 匹配 前j-1个模式，就为true
                dp[i][j] = dp[i-1][j-1];
        }
    }
    
    return dp[s_len][p_len];
}

int main()
{
    string pattern, str;
    
    cin >> pattern >> str;
    
    if(iteration_match(pattern, str))
        cout << "true" << endl;
    else
        cout << "false" << endl;
    
    return 0;
}