通配符
通配符可用于代替单个或多个字符 。通常地，星号
*匹配0个或以上的字符，问号?匹配1个字符。
命令行应用
dengy Test $ ls
1001.cpp 1001.exe* 1002.cpp 1002.exe* f1 f10 f100 f2 f20 f3 f5
dengy Test $ ls f?
f1 f2 f3 f5
dengy Test $ ls f*
f1 f10 f100 f2 f20 f3 f5
dengy Test $ rm *.exe
dengy Test $ ls
1001.cpp 1002.cpp f1 f10 f100 f2 f20 f3 f5
通配符用来模糊搜索文件。当查找文件夹时，可以使用它来代替一个或多个真正字符；当不知道真正字符或者懒得输入完整名字时，常常使用通配符代替一个或多个真正的字符。功能强大。 详细用法
DP算法实现
问题描述
给定字符串w，s。判断通配符范式w是否与字符串s相对应。
“*”是个问题
事先无法确定“ * ”对应几个字符。解决：将包含m个“ * ”的范式分解成m+1部分，“此范式是否对应字符串”问题分解为m+1个子问题。例如：范式 t*l?*o*r?ng*s 可分为 {t*, l?*, o*, r?ng*, s} 5部分。给出字符串 s = “thelordoftherings” 时，为了找出s中有几个字符对应第一个分割块，穷举搜索法会尝试所有可能组合。找出对应第一个分割块的3个字符后，递归调用判断”lordoftherings”是否对应余下4个块。
代码1
// thelordoftherings t*l?*o*r?ng*s
bool match(const string& w, const string& s)
{
//cout<<w<<" "<<s<<endl;
int pos = 0;
while(pos<w.size() && pos<s.size() && (w[pos]=='?'
|| w[pos]==s[pos]))
{
pos++;
}
if(pos == w.size())
{
return pos == s.size();
}
if(w[pos] == '*')
{
for(int skip=0; skip+pos<=s.size(); skip++)
{
if(match(w.substr(pos+1),s.substr(pos+skip)))
{
return true;
}
}
}
return false;
}
w和s不再匹配时，退出while，有以下情况。
- w[pos] != s[pos]：对应失败。
- 匹配完了w最后一个字符。此时w和s必须完全相等才能成立对应关系。
- 匹配完了s最后一个字符，w有剩余。此时剩余必须全为“*”相等才能成立对应关系。
- w[pos]为“*”。因未知“*”对应几个字符，所以利用0~len(剩余字符)循环检索所有可能性。
注意：代码中情况3合并到了情况4。
记忆化DP 制表
当输入为 w = “****a”，s = “aaaaaaab”时，存在大量重复计算。所以把计算过的值存入cache表。
int cache[101][101];
string S = "aaaab"; //"thelordoftherings";
string W = "**a"; //"t*l?*o*r?ng*s";
bool mem_match(int w,int s)
{
int& ret = cache[w][s];
if(ret != -1)
return ret;
if(w<W.size() && s<S.size())
cout<<W.substr(w)<<" "<<S.substr(s)<<endl;
while(w<W.size() && s<S.size() && (W[w]=='?'
|| W[w]==S[s]))
{
w++;s++;
}
if(w == W.size())
{
return ret = (s == S.size());
}
if(W[w] == '*')
{
for(int skip=0; skip+w<S.size(); skip++)
{
if(mem_match(w+1,s+skip))
{
return ret = 1;
}
}
}
return ret = 0;
}
int main()
{
memset(cache, -1, sizeof(cache));
cout<<mem_match(0,0);
return 0;
}
参考
《算法问题实战策略》[韩] 具万宗
