字符串匹配问题

字符串匹配问题

编程实现在单词表中查找与已知单词最接近的单词：
（1） 如果单词表中有要查找的单词输出该单词的位置；
（2） 如果单词表中没有要查找的单词，输出与要查找的单词最接近的单词
(可能不止一个)。最接近的单词是指以下三种情况：
a) 两个单词仅仅相差一个字母，包括多一个或者少一个字母。如
question 和 queston;time 和 timee;
b) 两个单词中仅有两个字母位置是相反的。如:teacherhe和taecher
c) 两个单词仅有一个字母不同，如：hello和hallo。
这题其实分 两部分：

1️⃣ 如果单词表里有该单词 → 输出位置
2️⃣ 如果没有 → 找最接近的单词

“最接近”有 3种情况：

① 相差一个字母（增/删）

例如：

question
queston

或

time
timee

判断方法：

长度差 = 1

② 两个字母位置互换

例如：

teacher
taecher

判断：

恰好两个位置不同
且交换后相同

③ 只有一个字母不同

例如：

hello
hallo

判断：

长度相同
只有1个字符不同

一、解题思路

步骤：

输入单词表
输入待查单词

① 先查 是否完全相同

如果找到：

输出位置

② 如果没有找到：

遍历单词表判断 三种接近情况

二、C++实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool oneReplace(string a,string b)
{
if(a.size()!=b.size()) return false;

int cnt=0;

for(int i=0;i<a.size();i++)
if(a[i]!=b[i]) cnt++;

return cnt==1;
}

bool oneInsert(string a,string b)
{
if(abs((int)a.size()–(int)b.size())!=1) return false;

string s=a.size()>b.size()?a:b;
string t=a.size()>b.size()?b:a;

int i=0,j=0,cnt=0;

while(i<s.size() && j<t.size())
{
if(s[i]==t[j])
{
i++;j++;
}
else
{
cnt++;
i++;
}
}

return cnt<=1;
}

bool swapTwo(string a,string b)
{
if(a.size()!=b.size()) return false;

vector<int> pos;

for(int i=0;i<a.size();i++)
if(a[i]!=b[i])
pos.push_back(i);

if(pos.size()!=2) return false;

return a[pos[0]]==b[pos[1]] && a[pos[1]]==b[pos[0]];
}

int main()
{
vector<string> word={
"teacher","hello","time","question","apple"
};

string target;

cin>>target;

for(int i=0;i<word.size();i++)
{
if(word[i]==target)
{
cout<<"位置:"<<i<<endl;
return 0;
}
}

cout<<"最接近的单词:"<<endl;

for(string w:word)
{
if(oneReplace(w,target)||
oneInsert(w,target)||
swapTwo(w,target))
{
cout<<w<<endl;
}
}

return 0;
}

三、运行示例

单词表：

teacher hello time question apple

输入：

taecher

输出：

最接近的单词:
teacher

输入：

hallo

输出：

最接近的单词:
hello

输入：

time

输出：

位置:2