資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
