圖里的深度優(yōu)先搜索 +

String.startsWith(String)
String.startsWith(String, int index)

圖里的深度優(yōu)先搜索

17 Letter Combinations of a Phone Number
291 Word Pattern II
127 Word Ladder
126 Word Ladder II
79 Word Search
212 Word Search II

基于圖的深度優(yōu)先搜索

17. Letter Combinations of a Phone Number

時間復雜度：3digit.length()~4digit.length()

class Solution {
    String[][] map = { {},{}, {"a","b","c"}, {"d","e","f"}, {"g","h","i"}, {"j","k","l"}, {"m","n","o"},{"p","q","r","s"},{"t","u","v"},{"w","x","y", "z"}};
    public List<String> letterCombinations(String digits) {
        List<String> results = new ArrayList<>();
        if(digits==null || digits.length()==0)
            return results;
        helper(digits, 0, results, "");
        return results;
    }
    private void helper(String digits, int index, List<String> results, String result){
        if(result.length()==digits.length()){
            results.add(result);
            return;
        }
        int num = Integer.parseInt(digits.charAt(index)+"");
        for(int j=0; j<map[num].length; j++){
            helper(digits, index+1, results, result + map[num][j]);
        }
    }
}

如果有一個詞典(Dictionary)，要求組成的單詞都是詞典里的，如何優(yōu)化?
用 Trie 或者 Hash 都可以:
用Hash：可以先遍歷詞典 把前綴和單詞存入hashmap，然后搜索的時候判斷是不是在map里就可以了

291. Word Pattern II

Input: pattern = "abab", str = "redblueredblue"
Output: true
字符和單詞一一對應
Assume string length is n, and pattern string length is m.
Time complexity: the problem is more like slicing the string into m pieces. How many slicing ways?組合數(shù)Cnm. For each slice, it takes O(n) to validate. So the total complexity is O(n * C(nm))

class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Set<String> set = new HashSet<>();
        Map<Character, String> map = new HashMap<>();
        return helper(pattern, str, 0, 0, map, set);
    }
    private boolean helper(String pattern, String str, int indexp, int indexs, Map<Character, String> map, Set<String> set){
        if(indexp==pattern.length())
            return indexs==str.length();
        if(indexs==str.length())
            return indexp==pattern.length();
        char c = pattern.charAt(indexp);
        if(map.containsKey(c)){
            String matchString = map.get(c);
            if(str.startsWith(matchString, indexs))
                return helper(pattern, str, indexp+1, indexs+matchString.length(), map, set);
            return false;
        }else{
            for(int i=indexs; i<str.length(); i++){
                String checkString = str.substring(indexs, i+1);
                if(set.contains(checkString))
                    continue;
                map.put(c, checkString);
                set.add(checkString);
                if(helper(pattern, str, indexp+1, indexs+checkString.length() ,map, set))
                    return true;
                map.remove(c);
                set.remove(checkString);
            }
        }
        return false;
    }
}

127. Word Ladder

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>();
        for(String word : wordList){
            set.add(word);
        }
        // set.add(endWord);
        return bfs(beginWord, endWord, set);
    }
    private int bfs(String beginWord, String endWord, Set<String> set){
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int result = 0;
        Set<String> visited = new HashSet<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            result = result+1;
            for(int i=0; i<size; i++){
                String current = queue.poll();
                if(current.equals(endWord)){
                    return result;
                }
                // visited.add(current);
                for(String nextWord: nextWords(current, set)){
                    if(!visited.contains(nextWord)){
                        queue.offer(nextWord);
                        visited.add(nextWord);
                    }
                }
            }
        }
        return 0;
    }
    private List<String> nextWords(String word, Set<String> set){
        //這個操作的時間復雜度是 O(26*wordlength^2)
        List<String> result = new ArrayList<>();
        for(int i=0; i<word.length(); i++){
            for(char j='a'; j<='z'; j++){
                if(word.charAt(i)==j)
                    continue;
                String newWord = newword(word, i, j);
                if(set.contains(newWord))
                    result.add(newWord);   
            }
        }
        return result;
    }
    private String newword(String word, int index, char c){
        char[] chars = word.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
}

126. Word Ladder II

一定要在得到下一層結果時候就處理 不要在每次出隊的時候再處理 這樣能減少重復入隊

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> results = new ArrayList<>();
        Set<String> dict = new HashSet<>();
        for(String word: wordList){
            dict.add(word);    
        }
        dict.add(beginWord);
        Map<String, Integer> distances = new HashMap<>();
        bfs(endWord, dict, distances);
        List<String> temp = new ArrayList<String>();
        temp.add(beginWord);
        dfs(beginWord, endWord, dict, distances, results, temp);
        return results;
    }
    
    private void dfs(String beginWord, String endWord, 
                     Set<String> dict, Map<String, Integer> distances, 
                    List<List<String>> results, List<String> temp){
        //這里不用判斷是否訪問過 只用向距離終點更近的點走就可以
        if(beginWord.equals(endWord)){
            results.add(new ArrayList<String>(temp));
            return;
        }
        for(String next: nextWords(beginWord, dict)){
            if(distances.get(beginWord)>distances.get(next)){
                temp.add(next);
                dfs(next, endWord, dict, distances, results, temp);
                temp.remove(temp.size()-1);
            }
        }
    }
    
    private void bfs(String endWord, Set<String> dict, Map<String, Integer> distances){
        //map一方面存距離 另一方面存是否訪問過
        Queue<String> queue = new LinkedList<>();
        queue.offer(endWord);
        int dis = 0;
        distances.put(endWord, 0);
        while(!queue.isEmpty()){
            int size = queue.size();
            dis = dis+1;
            for(int i=0; i<size; i++){
                String current = queue.poll();
                for(String nextWord: nextWords(current, dict)){
                    if(!distances.containsKey(nextWord)){
                        distances.put(nextWord, dis);
                        queue.offer(nextWord);
                    } 
                }
            }
        }
    }
    
    private List<String> nextWords(String word,Set<String> set){
        List<String> result = new ArrayList<>();
        for(int i=0; i<word.length(); i++){
            for(char j='a'; j<='z'; j++){
                if(word.charAt(i)==j)
                    continue;
                String newWord = newword(word, i, j);
                if(set.contains(newWord)){
                    result.add(newWord);
                }       
            }
        }
        return result;
    }
    private String newword(String word, int index, char c){
        char[] chars = word.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
}

79. Word Search

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(find(board, i, j, word, visited, 0))
                    return true;
            }
        }
        return false;
    }
    private boolean isValid(char[][] board,int x, int y, boolean[][] visited){
        if(x>=0 && x<board.length && y>=0 && y<board[0].length && visited[x][y]==false)
            return true;
        return false;
    }
    private boolean find(char[][] board,int x, int y, String word, boolean[][] visited, int index){
        int[] dirx = {1,-1,0,0};
        int[] diry = {0,0,1,-1};
        if(index == word.length())
            return true;
        if(!isValid(board, x, y, visited))
            return false;

        if(word.charAt(index)!=board[x][y])
            return false;
        visited[x][y] = true;
        for(int i=0; i<4; i++){
            if(find(board, x+dirx[i], y+diry[i], word, visited, index+1))
                return true;
        }
        visited[x][y] = false;
        return false;
    }
}

212. Word Search II

  • 用hashmap
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> prefixs = new HashSet<>();
        Set<String> wordSet = new HashSet<>();
        for(int j=0; j<words.length; j++){
            String word = words[j];
            wordSet.add(word);
            for(int i=0; i<word.length(); i++){
                String prefix = word.substring(0, i+1);
                prefixs.add(prefix);
            }
        }
        boolean[][] visited = new boolean[board.length][board[0].length];
        Set<String> results = new HashSet<>();
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                visited[i][j] = true;
                helper(board, visited, i, j, prefixs, wordSet, results, String.valueOf(board[i][j]));
                visited[i][j] = false;
            }
        }
        return new ArrayList<String>(results);
    }
    private void helper(char[][] board, boolean[][] visited, int x, int y, Set<String> prefixs, Set<String> wordSet, Set<String> results, String temp){ 
        if(wordSet.contains(temp)){
            results.add(temp);
        }
        if(!prefixs.contains(temp))
            return;
        
        int[] dirx = {1,-1,0,0};
        int[] diry = {0,0,1,-1};
        for(int i=0; i<4; i++){
            if(isValid(board, x+dirx[i], y+diry[i], visited)){
                visited[x+dirx[i]][y+diry[i]] = true;
                helper(board, visited, x+dirx[i], y+diry[i], prefixs, wordSet, results, temp+board[x+dirx[i]][y+diry[i]]);
                visited[x+dirx[i]][y+diry[i]] = false;
            }
        }   
    }
    private boolean isValid(char[][] board,int x, int y, boolean[][] visited){
        if(x>=0 && x<board.length && y>=0 && y<board[0].length && visited[x][y]==false)
            return true;
        return false;
    }
}
  • 用trie
class Solution {
    static class TrieNode{
        TrieNode[] children;
        TrieNode(){
            children = new TrieNode[26];
        }
    }
    static TrieNode root;
    private static void build(String[] words){
        for(String word: words){
            builderHelper(word);
        }
    }
    private static void builderHelper(String word){
        TrieNode current = root;
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(current.children[index]==null)
                current.children[index] = new TrieNode();
            current = current.children[index];
        }
    }

    private static boolean startWith(String word){
        TrieNode current = root;
        for(char c : word.toCharArray()){
            int index = c - 'a';
            if(current==null || current.children[index]==null)
                return false;
            current = current.children[index];
        }
        return true;
    }

    public static List<String> findWords(char[][] board, String[] words) {
        Set<String> results = new HashSet<>();
        root = new TrieNode();
        build(words);
        Set<String> set = new HashSet<>();
        for(String s: words){
            set.add(s);
        }
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                StringBuilder sb = new StringBuilder();
                sb.append(board[i][j]);
                visited[i][j] = true;
                helper(i, j, board, set, results, sb, visited);
                visited[i][j] = false;
            }
        }
        List<String> solutions = new ArrayList<>();
        for(String s: results){
            solutions.add(s);
        }
        return solutions;
    }
    private static void helper(int row, int col, char[][] board, Set<String> set, Set<String> results, StringBuilder sb, boolean[][] visited){

        if(set.contains(sb.toString()))
            results.add(sb.toString());
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, -1, 1};
        for(int i=0; i<4; i++){
            int x = row + dirx[i];
            int y = col + diry[i];
            if(!valid(x, y, visited)){
                continue;
            }
            sb.append(board[x][y]);
            if(!startWith(sb.toString())){
                sb.deleteCharAt(sb.length()-1);
                continue;
            }
            visited[x][y] = true;
            helper(x, y, board, set, results, sb, visited);
            sb.deleteCharAt(sb.length()-1);
            visited[x][y] = false;
        }
    }
    private static boolean valid(int x, int y, boolean[][] visited){
        return x>=0 && x<visited.length && y>=0 && y<visited[0].length && !visited[x][y];
    }
}
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 背景 一年多以前我在知乎上答了有關LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪：刷leetcod...
    土汪閱讀 12,916評論 0贊 33
  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,854評論 0贊 10
  • 拄著一根拐杖 背起一簍簍石沙 拖著沉重的步伐 頂著雨淋日曬 默默地拾級而上 在陡峭崎嶇的山野間穿插 汗水早已濕透了...
    王小永_6be2閱讀 1,056評論 4贊 15
  • 從大學畢業(yè)到現(xiàn)在，算算已經(jīng)六年的時間。誠然、每個人的職場方向都不太相同，但是總能從理工科技、社會人文方面找出自己從...
    花滿樓閱讀 1,834評論 2贊 25

友情鏈接更多精彩內容