brute force way using java (construct graph)!


  • 0
    T
    class Solution {
        public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
             Map<String,Set<String>> map = new HashMap<>();
            if(words1.length!=words2.length){
                return false;
            }
             for(int i=0;i<pairs.length;i++){
                 if(map.containsKey(pairs[i][0])==false){
                     map.put(pairs[i][0],new HashSet<>());
                 }
                 if(map.containsKey(pairs[i][1])==false){
                     map.put(pairs[i][1],new HashSet<>());
                 }
                 map.get(pairs[i][0]).add(pairs[i][1]);
                 map.get(pairs[i][1]).add(pairs[i][0]);
             }
            
             for(int i=0;i<words1.length;i++){
                 if(words1[i].equals(words2[i])){
                     continue;
                 }
                 if(!map.containsKey(words1[i])){
                     return false;
                 }
                 if(!dfs(words1[i],words2[i],map,new HashSet<String>())){
                     return false; 
                 }
             }
            
            return true;
        }
        
        public boolean dfs(String start,String end,Map<String,Set<String>> map,Set<String> set){
            if(start.equals(end)){
                return true;
            }
            
            if(set.contains(start)){
                return false;
            }
            set.add(start);
            for(String next_start:map.get(start)){
                if(dfs(next_start,end,map,set)){
                    return true;
                }
            }
            set.remove(start);
            
            return false;
        }
    }
    
    

Log in to reply
 

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