My Java Solution using hashMap and backtracking 163ms


  • 10

    The idea is borrowed from the discussion(https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16) , which is to first calculating all possible prefix, then do backtracking.

    We can use Trie or hashMap to store the prefix information, while I think Trie might be more hard to implement, without saving any space. So I use hashMap to store prefix information.

    public class Solution {
        public List<List<String>> wordSquares(String[] words) {
            List<List<String>> ret = new ArrayList<List<String>>();
            if(words.length==0 || words[0].length()==0) return ret;
            Map<String, Set<String>> map = new HashMap<>();
            int squareLen = words[0].length();
            // create all prefix
            for(int i=0;i<words.length;i++){
                for(int j=-1;j<words[0].length();j++){
                    if(!map.containsKey(words[i].substring(0, j+1))) map.put(words[i].substring(0, j+1), new HashSet<String>());
                    map.get(words[i].substring(0, j+1)).add(words[i]);
                }
            }
            helper(ret, new ArrayList<String>(), 0, squareLen, map);
            return ret;
        }
        public void helper(List<List<String>> ret, List<String> cur, int matched, int total, Map<String, Set<String>> map){
            if(matched == total) {ret.add(new ArrayList<String>(cur));return;}
            // build search string
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<=matched-1;i++) sb.append(cur.get(i).charAt(matched));
            // bachtracking
            Set<String> cand = map.get(sb.toString());
            if(cand==null) return;
            for(String str:cand){
                cur.add(str);
                helper(ret, cur, matched+1, total, map);
                cur.remove(cur.size()-1);
            }
        }
    }
    

  • 1
    G

    ....你头像是小松菜奈嘛


  • 0
    Y

    @YuTingLiu Thank you so much for your sharing. All of your solutions are really helpful. Thank you.


  • 0
    D

    You can save some space by change the map to Map<String, Set<Integer>>, map value is index list


  • 0
    J

    after changing the last line '''cur.remove(cur.size()-1);'''
    to
    '''cur.remove(str);'''
    i cannot pass some test. Could anyone explain to me why?

    Thank you!


Log in to reply
 

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