三刷 06/2022
Version #1 DFS
N - String length
Time O(N * N!) - copy string takes O(N) time * N! permutations
Space O(N) depth of the stack
一个可以改进的地方
private Map<Character, String> letters = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
Runtime: 2 ms, faster than 61.89% of Java online submissions for Letter Combinations of a Phone Number.
Memory Usage: 42.1 MB, less than 76.74% of Java online submissions for Letter Combinations of a Phone Number.
class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
Map<Character, List<Character>> map = Map.of(
'2', Arrays.asList(new Character[]{'a', 'b', 'c'}),
'3', Arrays.asList(new Character[]{'d', 'e', 'f'}),
'4', Arrays.asList(new Character[]{'g', 'h', 'i'}),
'5', Arrays.asList(new Character[]{'j', 'k', 'l'}),
'6', Arrays.asList(new Character[]{'m', 'n', 'o'}),
'7', Arrays.asList(new Character[]{'p', 'q', 'r', 's'}),
'8', Arrays.asList(new Character[]{'t', 'u', 'v'}),
'9', Arrays.asList(new Character[]{'w', 'x', 'y', 'z'}));
dfs(digits.toCharArray(), 0, map, new StringBuilder(), result);
return result;
}
private void dfs(char[] digits, int index, Map<Character, List<Character>> map, StringBuilder sb, List<String> result) {
if (index == digits.length) {
result.add(sb.toString());
return;
}
List<Character> letters = map.get(digits[index]);
for (Character letter : letters) {
sb.append(letter);
dfs(digits, index + 1,map, sb, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}
一刷
Version #1 DFSTime TreeDFS depth = length of digits => n
each node has about b children => branching factor = 3
Size of tree is b^n
O(b^n) => b = [3,4]
Space O(n) => depth of tree
27.73 %
public class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return new ArrayList<String>();
//key->digit value->array of chars
Map<Character, char[]> map = new HashMap<Character, char[]>();
map.put('0', new char[] {});
map.put('1', new char[] {});
map.put('2', new char[] { 'a', 'b', 'c' });
map.put('3', new char[] { 'd', 'e', 'f' });
map.put('4', new char[] { 'g', 'h', 'i' });
map.put('5', new char[] { 'j', 'k', 'l' });
map.put('6', new char[] { 'm', 'n', 'o' });
map.put('7', new char[] { 'p', 'q', 'r', 's' });
map.put('8', new char[] { 't', 'u', 'v'});
map.put('9', new char[] { 'w', 'x', 'y', 'z' });
List<String> result = new ArrayList<>();
dfs(digits, new StringBuilder(), 0, map, result);
return result;
}
private void dfs(String digits, StringBuilder path, int index, Map<Character, char[]> map, List<String> result) {
if (index == digits.length()) {
result.add(path.toString());
return;
}
char[] set = map.get(digits.charAt(index));
for (char c : set) {
path.append(c);
dfs(digits, path, index + 1, map, result);
path.deleteCharAt(path.length() - 1);
}
}
}
二刷
Golang DFS
Runtime: 0 ms, faster than 100.00% of Go online submissions for Letter Combinations of a Phone Number.
Memory Usage: 2 MB, less than 45.52% of Go online submissions for Letter Combinations of a Phone Number.
func letterCombinations(digits string) []string {
if digits == "" {
return []string{}
}
m := map[string][]string{
"2": []string{"a", "b", "c"},
"3": []string{"d", "e", "f"},
"4": []string{"g", "h", "i"},
"5": []string{"j", "k", "l"},
"6": []string{"m", "n", "o"},
"7": []string{"p", "q", "r", "s"},
"8": []string{"t", "u", "v"},
"9": []string{"w", "x", "y", "z"},
}
result := []string{}
dfs(0, digits, "", m, &result)
return result
}
func dfs(index int, digits string, path string, m map[string][]string, res *[]string) error {
// fmt.Printf("path: %s\n", path)
if index == len(digits) {
*res = append(*res, path)
return nil
}
list, ok := m[string(digits[index])]
if !ok {
return fmt.Errorf("invalid char: %s", digits[index])
}
for _, c := range list {
dfs(index + 1, digits, path + c, m, res)
}
return nil
}
No comments:
Post a Comment