2022-07-11

[Zheaoli]

2022-07-11

[SaraadKun]

676. 实现一个魔法字典

class MagicDictionary {

    private Trie dict = new Trie();

    public MagicDictionary() {

    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            dict.add(word);
        }
    }

    public boolean search(String searchWord) {
        return search(dict, searchWord.toCharArray(), 0, false);
    }

    private boolean search(Trie trie, char[] word, int index, boolean flag) {
        if (index == word.length) {
            return flag && trie.isEnd;
        }
        int idx = word[index] - 'a';
        //加一下非空判断,优先dfs当前位置单词非空的路径
        if (trie.children[idx] != null) {
            if (search(trie.children[idx], word, index + 1, flag)) {
                return true;
            }
        }
        //若未替换过字母,则可以替换字母后再搜,否则会出现如果字典里存在长度一样的单词都会返回true的情况
        if (!flag) {
            for (int i = 0; i < 26; i++) {
                //跳过i = idx的循环,上面已经搜过了
                if (i == idx || trie.children[i] == null) {
                    continue;
                }
                boolean res = search(trie.children[i], word, index + 1, true);
                if (res == true) {
                    return true;
                }
            }
        }
        return false;
    }

    static class Trie {

        private Trie[] children = new Trie[26];
        private boolean isEnd = false;

        public Trie(){}

        public void add(String word) {
            Trie cur = this;
            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';
                if (cur.children[idx] == null) {
                    cur.children[idx] = new Trie();
                }
                cur = cur.children[idx];
            }
            cur.isEnd = true;
        }

    }

}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

---

WeChat: Saraad

[SaraadKun]

752. 打开转盘锁752. 打开转盘锁

class Solution {

    int[] dirs = {-1, 1};

    public int openLock(String[] deadends, String target) {
        Set<Integer> set = new HashSet<>();
        for (String deadend : deadends) {
            set.add(Integer.parseInt(deadend));
        }
        //面向测试用例的编程
        if (set.contains(0)) {
            return -1;
        }
        if ("0000".equals(target)) {
            return 0;
        }
        int t = Integer.parseInt(target);
        //bfs,4个位置,每次只增加(or减小)1步,随机落在每个位置上
        //q中存放长度为5的int数组, arr[4]为步数,[arr[0], arr[3]]分别表示左起第1-4位的数字
        boolean[] visited = new boolean[10000];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0, 0, 0, 0});
        visited[0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int step = cur[4];
            for (int dir : dirs) {
                for (int i = 0; i < 4; i++) {
                    int n = 0;
                    for (int j = 0; j < 4; j++) {
                        if (j == i) {
                            n = n * 10 + (cur[j] + dir + 10) % 10;
                        } else {
                            n = n * 10 + cur[j];
                        }
                    }
                    if (t == n) {
                        return step + 1;
                    }
                    if (!visited[n] && !set.contains(n)) {
                        q.offer(new int[] {n / 1000, n / 100 % 10, n / 10 % 10, n % 10, step + 1});
                        visited[n] = true;
                    }
                }
            }
        }
        return -1;
    }
}

---

WeChat: Saraad