"word"와 같은 문자열이 있고 다음 약어가 포함되어 있다고 가정합니다. ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]. 또한 사전에 대상 문자열과 문자열 집합이 있습니다. 사전에 있는 문자열의 약어와 충돌하지 않도록 가능한 가장 작은 길이로 이 대상 문자열의 약어를 찾아야 합니다. 여기서 약어의 각 숫자 또는 문자는 길이 =1로 간주됩니다. 따라서 예를 들어 약어 "a32bc"는 길이 =4입니다.
따라서 입력이 "apple"과 같고 사전이 ["blade"]이면 출력은 "a4"
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
배열 사전 정의
-
abbrLen() 함수를 정의하면 마스크가 필요합니다.
-
렛 :=n
-
초기화 b :=3의 경우 b
를 수행합니다. -
(마스크 AND b)가 0과 같으면 -
-
(ret 1 감소)
-
-
-
리턴 렛
-
dfs() 함수를 정의하면 비트, 마스크,
가 필요합니다. -
len :=abbrLen(마스크)
-
len>=minLen이면 -
-
반환
-
-
일치 :=참
-
dict의 각 d에 대해 다음을 수행합니다. -
-
(마스크 AND d)가 0과 같으면 -
-
일치 :=거짓
-
루프에서 나오세요
-
-
-
일치가 0이 아닌 경우 -
-
minLen :=len
-
미나브 :=마스크
-
-
그렇지 않으면 -
-
초기화 b :=비트의 경우 b
-
(cand AND b)가 0이 아닌 경우 -
-
dfs(b*2, 마스크 OR b)
-
-
-
-
주요 방법에서 다음을 수행하십시오 -
-
ret :=빈 문자열
-
n :=타겟의 크기
-
bn :=2^n
-
캔디 :=0
-
minLen :=inf
-
사전의 각 s에 대해 -
-
s의 크기가 n과 같지 않으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
단어 :=0
-
initialize i :=0의 경우, i
-
s[i]가 target[i]와 같지 않으면 -
-
단어 :=단어 OR (2^i)
-
-
-
dict의 끝에 단어 삽입
-
cand :=cand OR 단어
-
-
dfs(1, 0)
-
초기화 i :=0, i
-
(minab AND 2^i)가 0과 같지 않으면 -
-
렛 :=렛 + 타겟[i]
-
(i를 1씩 증가)
-
-
그렇지 않으면
-
j :=나는
-
동안 (i
-
(i를 1씩 증가)
-
-
ret :=ret 연결(i - j)
-
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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