How to analyze the time/space complexity for this problem?


  • 1
    S

    public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
    ArrayList<String> res = new ArrayList<String>();
    if (board == null || board.length == 0 || board[0].length == 0) {
    return res;
    }
    HashSet<String> set = new HashSet<String>();
    Trie t = new Trie();
    for (String item : words) {
    t.insert(item);
    }
    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++) {
    dfs(board, visited, t, i, j, new StringBuilder(), set);
    }
    }
    return new ArrayList<String>(set);
    }

    public void dfs(char[][] board, boolean [][]visited, Trie t, int i, int j, StringBuilder sb, HashSet<String> set) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] == true) {
            return;
        }
        sb.append(board[i][j]);
        visited[i][j] = true;
        String str = sb.toString();
        if (t.startsWith(str)) {
            if (t.search(str)) {
                set.add(str);
            }
            dfs(board, visited, t, i + 1, j, sb, set);
            dfs(board, visited, t, i, j + 1, sb, set);
            dfs(board, visited, t, i - 1, j, sb, set);
            dfs(board, visited, t, i, j - 1, sb, set);
        }
        visited[i][j] = false;
        sb.deleteCharAt(sb.length() - 1);
    }
    
    
    private class Trie{
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();           
        }
        
        private class TrieNode{
            private char val;
            private TrieNode son[];
            private boolean isEnd;
            
            public TrieNode() {
                son = new TrieNode[26];
                isEnd = false;
            }
        } 
        
        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            TrieNode node = root;
            char[] letters = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                int pos = (int)(letters[i] - 'a');
                if (node.son[pos] == null) {
                    node.son[pos] = new TrieNode();
                    node.son[pos].val = letters[i];
                }
                node = node.son[pos];
            }
            node.isEnd = true;
        }
        
        public boolean startsWith(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            TrieNode node = root;
            char []letters = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                int pos = (int)(letters[i] - 'a');
                if (node.son[pos] == null) {
                    return false;
                }
                node = node.son[pos];
            }
            return true;
        }
        
        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            TrieNode node = root;
            char []letters = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                int pos = (int)(letters[i] - 'a');
                if (node.son[pos] == null) {
                    return false;
                }
                node = node.son[pos];
            }
            return node.isEnd;
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.