320. Generalized Abbreviation

public class Solution {
    public IList<string> GenerateAbbreviations(string word) {
        var ans = new List<string>();
        for (int x = 0; x < (1 << word.Length); ++x)
            ans.Add(Abbr(word, x));
        return ans;
    }
    private string Abbr(string word, int x) {
        var builder = new StringBuilder();
        int k = 0, n = word.Length;
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder.Append(k);
                    k = 0;
                }
                builder.Append(word[i]);
            } else {
                ++k;
            }
        }
        if (k != 0) builder.Append(k);
        return builder.ToString();
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> GenerateAbbreviations(string word) {
        var ans = new List<string>();
        for (int x = 0; x < (1 << word.size()); ++x)
            ans.push_back(Abbr(word, x));
        return ans;
    }
    private string Abbr(string word, int x) {
        var builder = new StringBuilder();
        int k = 0, n = word.size();
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder.Append(k);
                    k = 0;
                }
                builder.Append(word[i]);
            } else {
                ++k;
            }
        }
        if (k != 0) builder.Append(k);
        return builder.ToString();
    }
}

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        for (int x = 0; x < (1 << word.length()); ++x)
            ans.add(abbr(word, x));
        return ans;
    }

    private String abbr(String word, int x) {
        StringBuilder builder = new StringBuilder();
        int k = 0, n = word.length();
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder.append(k);
                    k = 0;
                }
                builder.append(word.charAt(i));
            } else {
                ++k;
            }
        }
        if (k != 0) builder.append(k);
        return builder.toString();
    }
}

var generateAbbreviations = function(word) {
    const result = [];
    const n = word.length;
    
    for (let x = 0; x < (1 << n); x++) {
        result.push(abbr(word, x));
    }
    
    return result;
};

var abbr = function(word, x) {
    let builder = '';
    let k = 0;
    const n = word.length;
    
    for (let i = 0; i < n; i++, x >>= 1) {
        if ((x & 1) === 0) {
            if (k !== 0) {
                builder += k;
                k = 0;
            }
            builder += word[i];
        } else {
            k++;
        }
    }
    
    if (k !== 0) builder += k;
    return builder;
};

console.log(generateAbbreviations("word"));

class Solution:
    def generateAbbreviations(self, word: str):
        def abbr(word, x):
            builder = []
            k = 0
            for i in range(len(word)):
                if x & 1 == 0:
                    if k != 0:
                        builder.append(str(k))
                        k = 0
                    builder.append(word[i])
                else:
                    k += 1
                x >>= 1
            if k != 0:
                builder.append(str(k))
            return ''.join(builder)
        
        ans = []
        for x in range(1 << len(word)):
            ans.append(abbr(word, x))
        return ans

package main

import (
    "fmt"
    "strconv"
)

func generateAbbreviations(word string) []string {
    n := len(word)
    var result []string

    for x := 0; x < (1 << n); x++ {
        result = append(result, abbr(word, x))
    }
    return result
}

func abbr(word string, x int) string {
    var builder []byte
    k := 0

    for i := 0; i < len(word); i, x = i+1, x>>1 {
        if x&1 == 0 {
            if k != 0 {
                builder = append(builder, strconv.Itoa(k)...)
                k = 0
            }
            builder = append(builder, word[i])
        } else {
            k++
        }
    }
    if k != 0 {
        builder = append(builder, strconv.Itoa(k)...)
    }
    return string(builder)
}

func main() {
    word := "word"
    fmt.Println(generateAbbreviations(word))
}

Algorithm

Создание битовых масок

Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

Генерация аббревиатур

Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.

Перебор всех комбинаций

Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎