[LeetCode]Generalized Abbreviation

ZoomQuiet 發(fā)布于2019-08-14 15:08 / 2169人閱讀

摘要：分析這道題第一步一定要理解題意，首先要考慮的是會有多少種結果。仔細觀察會發(fā)現(xiàn)，最終會有種結果。然后就很顯然應該用每次存下當前結果，然后繼續(xù)。

Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", >"1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

分析

這道題第一步一定要理解題意，首先要考慮的是會有多少種結果。仔細觀察會發(fā)現(xiàn)，最終會有Cn0 + Cn1 + Cn2 + ... + Cnn = 2^n種結果。
然后就很顯然應該用DFS, 每次recursion存下當前結果，然后繼續(xù)DFS。要注意下一步DFS的起始位置要與當前結束位置隔一個，否則就會出現(xiàn)有連續(xù)數(shù)字的結果，不希望出現(xiàn)連續(xù)數(shù)字的原因是因為連續(xù)數(shù)字可以合并成一個數(shù)字，已經(jīng)算進去了，比如ab111就是ab3, 我們要的結果是ab3。

復雜度

time: O(2^n), space: O(n)

代碼

public class Solution {
    public List generateAbbreviations(String word) {
        List res = new ArrayList<>();
        dfs(res, "", 0, word);
        return res;
    }
    
    public void dfs(List res, String curr, int start, String s) {
        res.add(curr + s.substring(start));                   
        if (start == s.length()) 
            return;
                                                
        // 定義新的起始位置
        int i = 0;
        
        // 除了最開始，起始位置都要與之前結尾位置隔一個
        if (start > 0) {
            i = start + 1;
        }
        
        for (; i < s.length(); i++) {
            String prefix = curr + s.substring(start, i);               
            // 以ith字符開頭，依次替換j個字母成數(shù)字。
            for (int j = 1; j <= s.length() - i; j++) {
                dfs(res,  prefix+ j, i + j, s);
            }
        }
    }
}

GPU云服務器云服務器 Generalized Abbreviation LeetCode LeetCode_String

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/65333.html

320. Generalized Abbreviation

摘要：題目鏈接要輸出所有的結果，標準思路。也可以做，保留為，改為數(shù)字的為，然后結果就是這么多，每個數(shù)學遍歷一遍求對應的即可。 320. Generalized Abbreviation 題目鏈接：https://leetcode.com/problems... 要輸出所有的結果，backtracking標準思路。 public class Solution { public List...

yangrd 2019-08-14 17:27 評論0 收藏0
320. Generalized Abbreviation and 22. Generate Par

320 Generalized Abbreviation public class Solution { public List generateAbbreviations(String word) { List res = new ArrayList(); backtrack(res, word, 0, , 0); return res; ...

lanffy 2019-08-14 17:59 評論0 收藏0
[LeetCode] 408. Valid Word Abbreviation

Problem Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation. A string such as word contains only the following valid abbreviations: [word...

zone 2019-08-16 13:44 評論0 收藏0
Word Abbreviation

摘要：鏈接注意第一個數(shù)字是的情況，這種也是不合法的。還有一個注意的就是要想和有相同的縮寫，長度必須和它相同，所以只保留長度相同的。注意剪枝，當前長度已經(jīng)超過就不需要繼續(xù)了。二進制的做法是這樣的，先對字典里面的單詞進行處理。 Valid Word Abbreviation 鏈接：https://leetcode.com/problems... 注意第一個數(shù)字是0的情況，[a, 01]這種也是不...

Y3G 2019-08-14 17:19 評論0 收藏0
[Leetcode] Encode and Decode Strings 字符串編解碼

摘要：記錄長度法復雜度時間空間思路本題難點在于如何在合并后的字符串中，區(qū)分出原來的每一個子串。這里我采取的編碼方式，是將每個子串的長度先賦在前面，然后用一個隔開長度和子串本身。這樣我們先讀出長度，就知道該讀取多少個字符作為子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...

gself 2019-08-14 12:36 評論0 收藏0