LeetCode(63) -- 20, 138, 139

P20. Valid Parentheses (Easy))

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

我的思路

用三个整数来记录开闭括号的次数。

我的代码

public class E_20_ValidParentheses {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        char[] chars = s.toCharArray();
        int j = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') {
                stack[j++] = chars[i];
            } else {
                if (j == 0 || stack[j - 1] != getOpen(chars[i])) {
                    return false;
                } else {
                    j--;
                }
            }
        }
        return j == 0;
    }

    private char getOpen(char c) {
        if (c == ')') return '(';
        if (c == ']') return '[';
        if (c == '}') return '{';
        return 0;
    }
}

100%

P138. Copy List with Random Pointer (Medium)

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

讨论区的思路

遍历这个list三次。第一次，复制每个节点（及其value），并且把它放到原节点的右边； 第二次，把原节点的random的指针的下一个，赋给新节点的random； 第三次，把新生成的这些节点连接到一个新的list中，并与原list脱钩。

最优解

public class M_138_CopyListwithRandomPointer {
    public Node copyRandomList(Node head) {
        Node curr = head;
        while (curr != null) {
            Node copy = new Node();
            copy.val = curr.val;
            copy.next = curr.next;
            curr.next = copy;
            curr = curr.next.next;
        }
        curr = head;

        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        curr = head;
        Node ans = new Node();
        Node copyCurr = ans;
        while (curr != null) {
            copyCurr.next = curr.next;
            copyCurr = copyCurr.next;
            curr.next = curr.next.next;
            curr = curr.next;
        }
        return ans.next;
    }
}

100%

P139. Word Break (Medium)

给一个长单词和一个字典，问这个长单词能否拆分成字典里的词。

我的思路

首先想到用Trie来记录一下字典里的单词。问题的关键在于，如果遇到一个完整的单词后，到底要不要拆。

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

比如这种情况，遇到cat后要不要拆？还是在cats拆？然后感觉像是DFS了，没思路了。

讨论区

public class M_139_WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> dict = new HashSet<>(wordDict);
        boolean[] word = new boolean[s.length() + 1];
        word[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (word[j] && dict.contains(s.substring(j, i))) {
                    word[i] = true;
                    break;
                }
            }
        }
        return word[s.length()];
    }
}

58%，就是把所有的字母的两两组合全试一遍，只要前面成功了，就只看新加的部分就行了。

最优解

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean bad[] = new boolean[s.length()];
        return wordBreak(s, 0, wordDict, bad);
    }

    public boolean wordBreak(String s, int offset, List<String> wordDict, boolean[] bad){
        if(s.length() == offset ){
            return true;
        }
        if(bad[offset]) return false;
        for(String dict: wordDict){
            if(s.startsWith(dict, offset)){
                if(wordBreak(s, offset + dict.length(), wordDict, bad)) return true;
            }
        }
        bad[offset] = true;
        return false;
    }
}

用了memo来存已经访问过的不成功的记录。这个方法一大亮点是用dict来遍历，而不是遍历长字符串。另外有一个startsWith(word, offset)方法值得学习，是从某个index开始，看是不是以某个字符串开头。这个方法在解析字符串时，可以省去不少操作。