[LeetCode]Generalized Abbreviation

ZoomQuiet 发布于2019-08-14 15:08 / 2122人阅读

摘要：分析这道题第一步一定要理解题意，首先要考虑的是会有多少种结果。仔细观察会发现，最终会有种结果。然后就很显然应该用每次存下当前结果，然后继续。

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"]

分析

这道题第一步一定要理解题意，首先要考虑的是会有多少种结果。仔细观察会发现，最终会有Cn0 + Cn1 + Cn2 + ... + Cnn = 2^n种结果。
然后就很显然应该用DFS, 每次recursion存下当前结果，然后继续DFS。要注意下一步DFS的起始位置要与当前结束位置隔一个，否则就会出现有连续数字的结果，不希望出现连续数字的原因是因为连续数字可以合并成一个数字，已经算进去了，比如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个字母成数字。
            for (int j = 1; j <= s.length() - i; j++) {
                dfs(res,  prefix+ j, i + j, s);
            }
        }
    }
}

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65333.html

320. Generalized Abbreviation

摘要：题目链接要输出所有的结果，标准思路。也可以做，保留为，改为数字的为，然后结果就是这么多，每个数学遍历一遍求对应的即可。 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

摘要：链接注意第一个数字是的情况，这种也是不合法的。还有一个注意的就是要想和有相同的缩写，长度必须和它相同，所以只保留长度相同的。注意剪枝，当前长度已经超过就不需要继续了。二进制的做法是这样的，先对字典里面的单词进行处理。 Valid Word Abbreviation 链接：https://leetcode.com/problems... 注意第一个数字是0的情况，[a, 01]这种也是不...

Y3G 2019-08-14 17:19 评论0 收藏0
[Leetcode] Encode and Decode Strings 字符串编解码

摘要：记录长度法复杂度时间空间思路本题难点在于如何在合并后的字符串中，区分出原来的每一个子串。这里我采取的编码方式，是将每个子串的长度先赋在前面，然后用一个隔开长度和子串本身。这样我们先读出长度，就知道该读取多少个字符作为子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...

gself 2019-08-14 12:36 评论0 收藏0