LC: 320. Generalized Abbreviation
https://leetcode.com/problems/generalized-abbreviation/
320. Generalized Abbreviation
A word's generalized abbreviation can be constructed by taking any number of non-overlapping substrings and replacing them with their respective lengths. For example, "abcde" can be abbreviated into "a3e" ("bcd" turned into "3"), "1bcd1" ("a" and "e" both turned into "1"), and "23" ("ab" turned into "2" and "cde" turned into "3").
Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.
Example 1:
Input: word = "word"
Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]Example 2:
Input: word = "a"
Output: ["1","a"]Constraints:
1 <= word.length <= 15wordconsists of only lowercase English letters.
The Essence:
Bei jedem Zeichen kann eine der zwei Entscheidungen getroffen werden: abkürzen oder bleiben lassen. Wenn man es abkürzt, inkrementiert man die Länge der schon bestimmten Abkürzung. Wenn man es bleiben lässt, dann fügt man die schon bestimmte Länge als Zeichen sowie das verarbeitete Zeichen zu dem String zu.
Um alle Möglichkeiten zu erledigen, kann der Algorithmus nach einer Entscheidung den String zu dem vorherigen Zustand zurückkehren.
Details:
Das hier beschriebene Verfahren ist ein Beispiel für einen Backtracking-Algorithmus. Nachdem man einige Entscheidungen getroffen hat, kann man die vorherige Entscheidung auf jeder Entscheidungsebene rückgängig machen, um die andere Entscheidung zu treffen. In der Implementation entspricht dies dem rekursiven Rückgängigmachen der Nebenwirkungen der vorherigen Entscheidung bis zur verarbeiteten Ebene, bei welcher schließlich die Gesamtergebnisse in einem Basis- bzw. Endfall gespeichert werden.
Solution(s) and Further Explanation:
Default Code:
Last updated