题解 | #字符串通配符#
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
#include<string> #include<iostream> #include<algorithm> #include<vector> using namespace std; /*统一大小写用transform 情况挺多,先在草稿搞清楚,再针对每种情况设计出对应的对策.不要合并太乱了 主要操作的2字符串的指针1j和2i,为了避免混乱就不要循环自加 同时函数judge判断结果,主函数再输出。 另外有可能有多种匹配情况,可能只有其中一种匹配上,所以当某一种匹配不上时, 需要继续尝试其他(记录所有可能新情况点,vector动态数组压入,尝试时出栈), 直到全部尝试都错才可以判错(vector为空)。尝试用递归调用judge,指针i\j可调,参数 */ //函数judge判断,2字符串指针j,i参数传入,默认0 0 bool judge(string s1, string s2,int i0=0,int j0=0) { int j = j0, i = i0; //2字符串指针初始化 vector<int>posi, posj; //记录分叉点,用于回溯 for (; j < s1.size() && i < s2.size();) { //遍历2字符串进行匹配 if (s1[j] == '?') { //匹配1字符符 if (isalnum(s2[i])) { //字符合法继续检查 i++, j++; } else { return false; //非法字符返回错 } } else if (s1[j] == '*') { //匹配不定长字符 if (s1[j + 1] == '*') { //连续**时,可以当做1个'*' j++; //**情况 } else if (s1[j+1]=='?') { //连续*?时,先匹配单字符该'?'为'*' j++; //*?情况 if(isalnum(s2[i])) i++; else return false; //特殊字符报错 s1[j]='*'; }else if (s1[j + 1] == s2[i]) { //记录地点 //匹配成功,将此时状态记录下来便于回溯 posi.push_back(i); posj.push_back(j); i++; j += 2; //找到下一对应字符,指针下移动 } else { //还未找到匹配的i指针,i指针下移继续匹配 if (isalnum(s2[i])) { i++; //当前字符串2字符合法,下移指针继续找对应 } else { return false; //非法字符 } } } else { //确定字符 if (s1[j++] != s2[i++]) { //字符不匹配,回溯更换匹配方式 if (!posi.empty()) { //回溯 i = posi.back() + 1; posi.pop_back(); //销毁该记录 j = posj.back(); posj.pop_back(); } else{ //用于回溯的记录为空,证明已无情况可回溯,已遍历全部匹配情况了,不匹配 return false; //匹配失败 } } } } if (i == s2.size() && (j == s1.size() || s1[s1.size() - 1] == '*' &&j == s1.size() - 1)) { return true; //结束字符串遍历看是否2字符串都遍历完或特殊情况 } else if (!posi.empty()) { //否则有误,需要回溯。若无回溯说明错误 i = posi.back() + 1; posi.pop_back(); j = posj.back(); posj.pop_back(); return judge(s1, s2,i,j); }else return false; } int main() { string s1, s2; cin >> s1 >> s2; //不区分大小写,需要统一 transform(s1.begin(), s1.end(), s1.begin(), ::tolower); transform(s2.begin(), s2.end(), s2.begin(), ::tolower); if (judge(s1, s2)) { cout << "true"; } else { cout << "false"; } return 0; }
#华为笔试#