LeetCode第17题 – 有效的括号

53 views

题目

解答

class Solution {
    public List<String> letterCombinations(char[] chars, int pos, Map<Character, String> mappings) {
        if (pos > chars.length - 1) {
            return Collections.emptyList();
        }

        char value = chars[pos];
        if (!mappings.containsKey(value)) {
            return letterCombinations(chars, pos + 1, mappings);
        }

        List<String> values2 = letterCombinations(chars, pos + 1, mappings);

        String mapping = mappings.get(value);

        List<String> values = new ArrayList<>();

        if (values2.isEmpty()) {
            for (int i = 0, length = mapping.length(); i < length; ++i) {
                values.add(String.valueOf(mapping.charAt(i)));
            }
        } else {
            for (int i = 0, length = mapping.length(); i < length; ++i) {
                final int j = i;

                values.addAll(
                        values2.stream().map(d -> String.valueOf(mapping.charAt(j)) + d).collect(Collectors.toList()));
            }
        }

        return values;
    }

    public List<String> letterCombinations(String digits) {

        Map<Character, String> mappings = new HashMap<>();
        mappings.put('2', "abc");
        mappings.put('3', "def");
        mappings.put('4', "ghi");
        mappings.put('5', "jkl");
        mappings.put('6', "mno");
        mappings.put('7', "pqrs");
        mappings.put('8', "tuv");
        mappings.put('9', "wxyz");
        char[] chars = digits.toCharArray();

        return letterCombinations(chars, 0, mappings);
    }
}

要点
使用递归很容易求解。
需要注意题目的输入中可能存在特殊字符1

准备的用例,如下

@Before
public void before() {
    t = new Solution();
}

@Test
public void test001() {
    List<String> lists = Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf").stream().sorted()
            .collect(Collectors.toList());

    assertEquals(lists, t.letterCombinations("23").stream().sorted().collect(Collectors.toList()));
}

@Test
public void test002() {
    List<String> lists = new ArrayList<>();

    assertEquals(lists, t.letterCombinations("").stream().sorted().collect(Collectors.toList()));
}

@Test
public void test003() {
    List<String> lists = Arrays.asList("a", "b", "c");

    assertEquals(lists, t.letterCombinations("2").stream().sorted().collect(Collectors.toList()));
}

@Test
public void test004() {
    List<String> lists = Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf").stream().sorted()
            .collect(Collectors.toList());

    assertEquals(lists, t.letterCombinations("213").stream().sorted().collect(Collectors.toList()));
}

@Test
public void test005() {
    List<String> lists = Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf").stream().sorted()
            .collect(Collectors.toList());

    assertEquals(lists, t.letterCombinations("123").stream().sorted().collect(Collectors.toList()));
}


若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第17题 – 有效的括号

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud