資訊專欄INFORMATION COLUMN
摘要：分析這道題第一步一定要理解題意，首先要考慮的是會(huì)有多少種結(jié)果。仔細(xì)觀察會(huì)發(fā)現(xiàn)，最終會(huì)有種結(jié)果。然后就很顯然應(yīng)該用每次存下當(dāng)前結(jié)果，然后繼續(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"]
這道題第一步一定要理解題意，首先要考慮的是會(huì)有多少種結(jié)果。仔細(xì)觀察會(huì)發(fā)現(xiàn)，最終會(huì)有Cn0 + Cn1 + Cn2 + ... + Cnn = 2^n種結(jié)果。
然后就很顯然應(yīng)該用DFS, 每次recursion存下當(dāng)前結(jié)果，然后繼續(xù)DFS。要注意下一步DFS的起始位置要與當(dāng)前結(jié)束位置隔一個(gè)，否則就會(huì)出現(xiàn)有連續(xù)數(shù)字的結(jié)果，不希望出現(xiàn)連續(xù)數(shù)字的原因是因?yàn)檫B續(xù)數(shù)字可以合并成一個(gè)數(shù)字，已經(jīng)算進(jìn)去了，比如ab111就是ab3, 我們要的結(jié)果是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;
// 除了最開始，起始位置都要與之前結(jié)尾位置隔一個(gè)
if (start > 0) {
i = start + 1;
}
for (; i < s.length(); i++) {
String prefix = curr + s.substring(start, i);
// 以ith字符開頭，依次替換j個(gè)字母成數(shù)字。
for (int j = 1; j <= s.length() - i; j++) {
dfs(res, prefix+ j, i + j, s);
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65333.html
摘要：題目鏈接要輸出所有的結(jié)果，標(biāo)準(zhǔn)思路。也可以做，保留為，改為數(shù)字的為，然后結(jié)果就是這么多，每個(gè)數(shù)學(xué)遍歷一遍求對(duì)應(yīng)的即可。 320. Generalized Abbreviation 題目鏈接：https://leetcode.com/problems... 要輸出所有的結(jié)果，backtracking標(biāo)準(zhǔn)思路。 public class Solution { public List...
320 Generalized Abbreviation public class Solution { public List generateAbbreviations(String word) { List res = new ArrayList(); backtrack(res, word, 0, , 0); return res; ...
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...
摘要：鏈接注意第一個(gè)數(shù)字是的情況，這種也是不合法的。還有一個(gè)注意的就是要想和有相同的縮寫，長(zhǎng)度必須和它相同，所以只保留長(zhǎng)度相同的。注意剪枝，當(dāng)前長(zhǎng)度已經(jīng)超過(guò)就不需要繼續(xù)了。二進(jìn)制的做法是這樣的，先對(duì)字典里面的單詞進(jìn)行處理。 Valid Word Abbreviation 鏈接：https://leetcode.com/problems... 注意第一個(gè)數(shù)字是0的情況，[a, 01]這種也是不...
摘要：記錄長(zhǎng)度法復(fù)雜度時(shí)間空間思路本題難點(diǎn)在于如何在合并后的字符串中，區(qū)分出原來(lái)的每一個(gè)子串。這里我采取的編碼方式，是將每個(gè)子串的長(zhǎng)度先賦在前面，然后用一個(gè)隔開長(zhǎng)度和子串本身。這樣我們先讀出長(zhǎng)度，就知道該讀取多少個(gè)字符作為子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...
閱讀 1311·2021-11-24 10:24
閱讀 4091·2021-11-22 15:29
閱讀 1085·2019-08-30 15:53
閱讀 2788·2019-08-30 10:54
閱讀 1977·2019-08-29 17:26
閱讀 1271·2019-08-29 17:08
閱讀 605·2019-08-28 17:55
閱讀 1576·2019-08-26 14:01
