An abbreviation of a word follows the form
- it --> it (no abbreviation)
- d|o|g --> d1g
- i|nternationalizatio|n --> i18n
- l|ocalizatio|n --> l10n
Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
Example:
- Given dictionary = [ "deer", "door", "cake", "card" ]
- isUnique("dear") -> false
- isUnique("cart") -> true
- isUnique("cane") -> false
- isUnique("make") -> true
C Solution:
struct He {
char start;
int middle;
char end;
char *str;
bool multi;
struct He *next;
};
struct ValidWordAbbr {
int size;
struct He **list;
};
struct ValidWordAbbr* ValidWordAbbrCreate(char** dictionary, int dictionarySize) {
struct ValidWordAbbr *vwa = malloc(sizeof(struct ValidWordAbbr));
vwa->size = 1000;
vwa->list = calloc(vwa->size, sizeof(struct He *));
int i;
for (i = 0; i < dictionarySize; i++) {
int len = strlen(dictionary[i]);
char start = dictionary[i][0];
char end = dictionary[i][len - 1];
len -= 2;
unsigned ind = start * 321 + len * 21 + end;
ind %= vwa->size;
struct He *p = vwa->list[ind];
while (p) {
if (p->start == start && p->end == end && p->middle == len) {
if (p->multi) break;
if (strcmp(dictionary[i], p->str)) {
p->multi = true;
break;
}
}
p = p->next;
}
if (p) continue;
p = malloc(sizeof(struct He));
p->start = start;
p->end = end;
p->middle = len;
p->multi = false;
p->str = dictionary[i];
p->next = vwa->list[ind];
vwa->list[ind] = p;
}
return vwa;
}
bool isUnique(struct ValidWordAbbr* vwa, char* word) {
int len = strlen(word);
char start = word[0];
char end = word[len - 1];
len -= 2;
unsigned ind = start * 321 + len * 21 + end;
ind %= vwa->size;
struct He *p = vwa->list[ind];
while (p) {
if (p->start == start && p->end == end && p->middle == len) {
if (p->multi) return false;
if (strcmp(word, p->str)) {
return false;
}
return true;
}
p = p->next;
}
return true;
}
void ValidWordAbbrFree(struct ValidWordAbbr* vwa) {
int i;
for (i = 0; i < vwa->size; i++) {
struct He *p = vwa->list[i], *q;
while (p) {
q = p->next;
free(p);
p = q;
}
}
free(vwa->list);
free(vwa);
}
Summary:
- If 'd1g' only contains 'dog', then isunique('dog') return true and isunique('dtg') return false.
- Using C to solve problems related to HashTable and string is painful.
- 49ms, 100% (depend on hash function and hashtable size)
LeetCode: 288. Unique Word Abbreviation
近期评论