数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的最小唯一单词缩写
假设我们有一个像“word”这样的字符串，它包含以下缩写：["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]。我们还有一个目标字符串和字典中的一组字符串，我们需要找到这个目标字符串的缩写，使其长度尽可能短，并且不与字典中字符串的缩写冲突。这里缩写中的每个数字或字母都被认为长度为 1。例如，缩写“a32bc”的长度为 4。
因此，如果输入类似于“apple”，并且字典为 ["blade"]，则输出将为“a4”
为了解决这个问题，我们将遵循以下步骤：
定义一个数组 dict
定义一个函数 abbrLen()，它将接收 mask 作为参数，
ret := n
初始化 b := 3，当 b < bn 时，更新 b <<= 1，执行以下操作：
如果 (mask AND b) 等于 0，则：
（将 ret 减 1）
返回 ret
定义一个函数 dfs()，它将接收 bit 和 mask 作为参数，
len := abbrLen(mask)
如果 len >= minLen，则：
返回
match := true
对于 dict 中的每个 d，执行以下操作：
如果 (mask AND d) 等于 0，则：
match := false
退出循环
如果 match 不为零，则：
minLen := len
minab := mask
否则：
初始化 b := bit，当 b < bn 时，更新 b := b*2，执行以下操作：
如果 (cand AND b) 不等于 0，则：
dfs(b*2, mask OR b)
从主方法执行以下操作：
ret := 空字符串
n := target 的大小
bn := 2^n
cand := 0
minLen := inf
对于字典中的每个 s，执行以下操作：
如果 s 的大小不等于 n，则：
忽略以下部分，跳过到下一个迭代
word := 0
初始化 i := 0，当 i < s 的大小时，更新 (i 增加 1)，执行以下操作：
如果 s[i] 不等于 target[i]，则：
word := word OR (2^i)
将 word 插入到 dict 的末尾
cand := cand OR word
dfs(1, 0)
初始化 i := 0，当 i < n 时，执行以下操作：
如果 (minab AND 2^i) 不等于 0，则：
ret := ret + target[i]
（i 增加 1）
否则
j := i
当 (i < n 且 (minab AND 2^i) 等于 0) 时，执行以下操作：
（i 增加 1）
ret := ret 连接 (i - j)
返回 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
248 次查看
