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