C ++中的最小唯一单词缩写
假设我们有一个字符串，例如“word”，其中包含以下缩写：[“word”，“1ord”，“w1rd”，“wo1d”，“wor1”，“2rd”，“w2d”，“wo2”，“1o1d”，“1or1”，“w1r1”，“1o2”，“2r1”，“3d”，“w3”，“4”]]。我们在字典中也有一个目标字符串和一组字符串，我们必须找到该目标字符串的缩写，且长度要尽可能短，以免与字典中字符串的缩写冲突。在这里，缩写中的每个数字或字母都被认为是length=1。因此，作为示例，缩写“a32bc”的长度为4。
因此，如果输入就像“苹果”，而字典是[“刀片”]，那么输出将是“a4”
为了解决这个问题，我们将遵循以下步骤-
定义数组字典
定义一个函数abbrLen()，它将带有掩码，
ret：=n
对于初始化b：=3，当b<bn时，更新b<<=1，执行-
（将retret减少1）
如果（maskANDb）等于0，则-
返回ret
定义一个函数dfs()，将需要位，掩码，
len：=abbrLen（掩码）
如果len>=minLen，则-
返回
匹配：=true
对于字典中的每个d，执行-
匹配：=否
从循环中出来
如果（maskANDd）等于0，则-
如果match为非零，则-
minLen：=len
minab：=面膜
否则-
如果（candANDb）不等于0，则-
dfs（b*2，遮罩或b）
对于初始化b：=位，当b<bn时，更新b：=b*2，执行-
从主要方法中执行以下操作-
ret：=空字符串
n：=目标大小
bn：=2^n
坎德：=0
minLen：=inf
对于字典中的每个s-
如果s[i]不等于target[i]，则-
单词：=单词OR（2^i）
忽略以下部分，跳至下一个迭代
如果s的大小不等于n，则-
字：=0
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
在字典末尾插入单词
cand：=candORword
dfs(1,0)
对于初始化i：=0，当i<n时-
j：=我
而（i<n和（minabAND2^i）等于0），-
ret：=ret级联(i-j)
（将i增加1）
ret：=ret+目标[i]
（将i增加1）
如果（minabAND2^i）不等于0，则-
除此以外
返回ret
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int n, cand, bn, minLen, minab;
vector<int> dict;
int abbrLen(int mask) {
int ret = n;
for (int b = 3; b < bn; b <<= 1) {
if ((mask & b) == 0)
ret--;
}
return ret;
}
void dfs(int bit, int mask) {
int len = abbrLen(mask);
if (len >= minLen)
return;
bool match = true;
for (int d : dict) {
if ((mask & d) == 0) {
match = false;
break;
}
}
if (match) {
minLen = len;
minab = mask;
}
else {
for (int b = bit; b < bn; b <<= 1) {
if ((cand & b) != 0)
dfs(b << 1, mask | b);
}
}
}
string minAbbreviation(string target, vector<string> &dictionary) {
string ret = "";
n = target.size();
bn = 1 << n;
cand = 0;
minLen = INT_MAX;
for (string &s : dictionary) {
if (s.size() != n)
continue;
int word = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != target[i])
word |= (1 << i);
}
dict.push_back(word);
cand |= word;
}
dfs(1, 0);
for (int i = 0; i < n;) {
if ((minab & (1 << i)) != 0) {
ret += target[i];
i++;
}
else {
int j = i;
while (i < n && (minab & (1 << i)) == 0)
i++;
ret += to_string(i - j);
}
}
return ret;
}
};
main() {
Solution ob;
vector<string> v = {"blade"};
cout << (ob.minAbbreviation("apple",v));
}输入项
"apple",{"blade"}输出结果
a4