README_EN.md

527. Word Abbreviation

中文文档

Description

Given an array of distinct strings words, return the minimal possible abbreviations for every word.

The following are the rules for a string abbreviation:

1. The initial abbreviation for each word is: the first character, then the number of characters in between, followed by the last character.
2. If more than one word shares the same abbreviation, then perform the following operation:
   • Increase the prefix (characters in the first part) of each of their abbreviations by 1.
     • For example, say you start with the words ["abcdef","abndef"] both initially abbreviated as "a4f". Then, a sequence of operations would be ["a4f","a4f"] -> ["ab3f","ab3f"] -> ["abc2f","abn2f"].
   • This operation is repeated until every abbreviation is unique.
3. At the end, if an abbreviation did not make a word shorter, then keep it as the original word.

 

Example 1:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

Example 2:

Input: words = ["aa","aaa"]
Output: ["aa","aaa"]

 

Constraints:

• 1 <= words.length <= 400
• 2 <= words[i].length <= 400
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Solutions

Python3

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.v = defaultdict(int)

    def insert(self, w):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            node.v[(w[-1], len(w))] += 1

    def search(self, w):
        node = self
        res = []
        for c in w[:-1]:
            idx = ord(c) - ord('a')
            node = node.children[idx]
            res.append(c)
            if node.v[(w[-1], len(w))] == 1:
                break
        n = len(w) - len(res) - 1
        if n:
            res.append(str(n))
        res.append(w[-1])
        t = ''.join(res)
        return t if len(t) < len(w) else w


class Solution:
    def wordsAbbreviation(self, words: List[str]) -> List[str]:
        trie = Trie()
        for w in words:
            trie.insert(w)
        return [trie.search(w) for w in words]

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.v = Counter()

    def insert(self, w):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            node.v[w[-1]] += 1

    def search(self, w):
        node = self
        res = []
        for c in w[:-1]:
            idx = ord(c) - ord('a')
            node = node.children[idx]
            res.append(c)
            if node.v[w[-1]] == 1:
                break
        n = len(w) - len(res) - 1
        if n:
            res.append(str(n))
        res.append(w[-1])
        t = ''.join(res)
        return t if len(t) < len(w) else w


class Solution:
    def wordsAbbreviation(self, words: List[str]) -> List[str]:
        trees = {}
        for w in words:
            if len(w) not in trees:
                trees[len(w)] = Trie()
        for w in words:
            trees[len(w)].insert(w)
        return [trees[len(w)].search(w) for w in words]

Java

class Trie {
    Trie[] children = new Trie[26];
    int[] v = new int[26];

    void insert(String w) {
        Trie node = this;
        int t = w.charAt(w.length() - 1) - 'a';
        for (char c : w.toCharArray()) {
            c -= 'a';
            if (node.children[c] == null) {
                node.children[c] = new Trie();
            }
            node = node.children[c];
            node.v[t]++;
        }
    }

    String search(String w) {
        Trie node = this;
        StringBuilder res = new StringBuilder();
        int t = w.charAt(w.length() - 1) - 'a';
        for (int i = 0; i < w.length() - 1; ++i) {
            char c = w.charAt(i);
            node = node.children[c - 'a'];
            res.append(c);
            if (node.v[t] == 1) {
                break;
            }
        }
        int n = w.length() - res.length() - 1;
        if (n > 0) {
            res.append(n);
        }
        res.append(w.charAt(w.length() - 1));
        return res.length() < w.length() ? res.toString() : w;
    }
}

class Solution {
    public List<String> wordsAbbreviation(List<String> words) {
        Map<Integer, Trie> trees = new HashMap<>();
        for (String w : words) {
            if (!trees.containsKey(w.length())) {
                trees.put(w.length(), new Trie());
            }
        }
        for (String w : words) {
            trees.get(w.length()).insert(w);
        }
        List<String> ans = new ArrayList<>();
        for (String w : words) {
            ans.add(trees.get(w.length()).search(w));
        }
        return ans;
    }
}

Go

type Trie struct {
	children [26]*Trie
	v        [26]int
}

func newTrie() *Trie {
	return &Trie{}
}
func (this *Trie) insert(w string) {
	node := this
	t := w[len(w)-1] - 'a'
	for _, c := range w {
		c -= 'a'
		if node.children[c] == nil {
			node.children[c] = newTrie()
		}
		node = node.children[c]
		node.v[t]++
	}
}
func (this *Trie) search(w string) string {
	node := this
	t := w[len(w)-1] - 'a'
	res := &strings.Builder{}
	for _, c := range w[:len(w)-1] {
		res.WriteRune(c)
		c -= 'a'
		node = node.children[c]
		if node.v[t] == 1 {
			break
		}
	}
	n := len(w) - res.Len() - 1
	if n > 0 {
		res.WriteString(strconv.Itoa(n))
	}
	res.WriteByte(w[len(w)-1])
	if res.Len() < len(w) {
		return res.String()
	}
	return w
}

func wordsAbbreviation(words []string) []string {
	trees := map[int]*Trie{}
	for _, w := range words {
		if _, ok := trees[len(w)]; !ok {
			trees[len(w)] = newTrie()
		}
	}
	for _, w := range words {
		trees[len(w)].insert(w)
	}
	ans := []string{}
	for _, w := range words {
		ans = append(ans, trees[len(w)].search(w))
	}
	return ans
}

...