Сложность: medium
Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.
Например, "abcde" можно сократить следующим образом:
"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:
"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.
Пример:
Input: word = "a"
Output: ["1","a"]
👨💻 Алгоритм:
1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.
2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.
3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.
😎 Решение:
class Solution {
public:
vector<string> generateAbbreviations(string word) {
vector<string> ans;
for (int x = 0; x < (1 << word.length()); ++x)
ans.push_back(abbr(word, x));
return ans;
}
private:
string abbr(const string& word, int x) {
string builder;
int k = 0, n = word.length();
for (int i = 0; i < n; ++i, x >>= 1) {
if ((x & 1) == 0) {
if (k != 0) {
builder += to_string(k);
k = 0;
}
builder += word[i];
} else {
++k;
}
}
if (k != 0) builder += to_string(k);
return builder;
}
};Ставь 👍 и забирай 📚 Базу знаний