JAVA 53ms, DFS + HashMap


  • 1
    I

    Straight forward DFS, with hash map storing words with same prefix.

    public List<List<String>> wordSquares(String[] words) {
        int n = words[0].length();
        Map<String, Set<String>> map = new HashMap<>();
        for (String w : words) {
            for (int i = 0; i < n; ++i) {
                String key = w.substring(0, i);
                Set<String> set = map.get(key);
                if (set == null) {
                    set = new HashSet<>();
                    map.put(key, set);
                }
                set.add(w);
            }
        }
        List<List<String>> ans = new LinkedList<>();
        dfs(0, n, new char[n][n], map, ans);
        return ans;
    }
    void dfs(int i, int n, char[][] m, Map<String, Set<String>> map, List<List<String>> ans) {
        if (i == n) {
            List<String> list = new ArrayList<>(n);
            for (int j = 0; j < n; ++j) list.add(new String(m[j]));
            ans.add(list);
            return;
        }
        for (String w : map.get(new String(m[i], 0, i))) {
            m[i][i] = w.charAt(i);
            int j = i + 1;
            for (; j < n; ++j) {
                m[i][j] = w.charAt(j);
                m[j][i] = w.charAt(j);
                if (!map.containsKey(new String(m[j], 0, i+1))) break;
            }
            if (j == n) dfs(i + 1, n, m, map, ans);
        }
    }
    

Log in to reply
 

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