Max Words Package


  • 4

    This is a interview problem I met on an onsite interview (actually the second round), which is defined by the interviewers the top-hard problems of their interview-problem library.

    Since I was rejected after the 8-round interview (one online test, three onsite algorithm problems and four culture fit interviews) and we had no agreement on sharing stuff, so here it is.

    Description

    You are given a NxN matrix composed of lowercase letters and a list of words. Your task is to find out the largest list of words that can be formed by the letters in the matrix.

    Constraints:

    • each letter can only be used once for a word;
    • once the cell (letter) in the matrix is taken by a word, then the other words in the same list cannot use that cell again.

    Example:

    Input:

    {
    {‘o’, ‘a’, ‘a’, ‘n’},
    {‘e’, ‘t’, ‘a’, ‘e’},
    {‘i’, ‘h’, ‘k’, ‘r’},
    {‘i’, ‘f’, ‘l’, ‘v’}
    }
    {“eat”, “oath”, “aak”, “ner”, “oei”, “thfl”}

    Output:

    {“oei”, “ner”, “aak”, “thfl”}

    Explanation:

    Actually all these words can be formed in the matrix, but we have to ensure the biggest list of words.

    • if we take “eat”, then the list should be {“eat”, “oei”};
    • if we take “oath”, then the list should be {“oath”, “aak”, “ner”};
    • if we take “aak”, then the list should be {“oei”, “aak”, “ner”, “thfl”};
      So we should return the biggest list {“oei”, “aak”, “ner”, “thfl”} as the final result.

  • 0
    M
    This post is deleted!

  • 0
    H

    We can Reduce this to finding the Maximal Independent set in a graph which is NP Complete.

    Vertices are words in the dictionary and edges are whether two words have a common character in the matrix (Assuming that a word can be formed only once)


  • 0
    
    class Node{
    	boolean isEnd;
    	int wrdIdx;
    	Node[] child;
    
    }
    
    public List<String> getWords(char[][] m, List<String> wrds){
    	Node n = buildTrie(wrds);
    	List<Integer>[] wrdsAtCell = (List<Integer>[]) new ArrayList[m.length][m[0].length];/**
    	Store the words that have a letter at each cell (using Integer instead of String because 
    	we are storing the index of the word as it appears in the input list (wrds))**/
    	for(int i = 0; i < wrdsAtCell.length; i++){
    		wrdsAtCell[i] = new ArrayList<Integer>();
    	}
    	for(int i = 0; i < m.length; i++){
    		for(int c = 0; c < m[0].length; c++){
    			dfs(i,c,m,n,wrdsAtCell,new ArrayList<Integer>());
    		
    		}
    	}
    	
    	Map<String,Set<String>> graph = new HashMap<String,Set<String>>();
    	for(int i = 0; i < wrds.size(); i++){
    		graph.put(wrds.get(i),new HashSet<String>);
    	}
    	//create a undirected graph where each edge represents a connection between two words that share a common cell in the input matrix.
    	for(List<Integer> ls:wrdsAtCell){
    	//Iterate through all words that have a letter in this cell and create edges between each pair of words in this list.
    		for(int i = 0; i < ls.size(); i++){
    			Set<String> curr = graph.get(wrds.get(ls.get(i)));
    			for(int j = i + 1; j < ls.size(); j++){
    				graph.get(wrds.get(ls.get(j))).add(wrds.get(ls.get(i)));
    				curr.add(wrds.get(ls.get(j)));
    			}
    		
    		}
    	}
    	
    	//Iterate through the graph, for each word that has 1 or more edges. Remove the edges that it forms with other words.
    	for(String s: wrds){
    		if(graph.get(s).size() >= 1){//If s has edges to more then one word, remove s from each of these words adjacency.
    			Iterator<String> st = graph.get(s).iterator();
    			while(st.hasNext()){
    				graph.get(st.next()).remove(s);
    			}
    		
    		}
    	}
    	List<String> results = new ArrayList<String>();
    	//Return a list of all words whose adjaceny size is 0,these are words that occur in cells which only belong to one word)
    	for(Map.Entry<String,Set<String>> e: graph.entrySet()){
    		if(e.getValue().isEmpty()){
    			results.add(e.getKey());
    		}
    	}
    	return results;
    }
    
    private Node buildTrie(List<String> wrds){
    	Node rt = new Node();
    	for(int i = 0; i < wrds.size(); i++){
    		addToTrie(i,wrds.get(i),rt);
    	}
    	return rt;
    
    }
    
    private void addToTrie(int idx, String s, Node n){
    	Node v = n;
    	for(int i = 0; i < s.length(): i++){
    		int charIdx = (int)(s.charAt(i) - 'a');
    		if(v.child[charIdx] == null){
    			v.child[charIdx] = new Node();
    		}
    		v = v.child[charIdx];
    	}
    	v.isEnd = true;
    	v.wordIdx = idx;
    }
    private void dfs(int r, int c, char[][] m, Node n,List<Integer>[] wrdsAtCell,List<Integer> path){
    	if(n.isEnd){
    		for(Integer i:path){
    			wrdsAtCell[i].add(n.wrdIndex);
    		
    		}
    		return;
    	}
    	int charIdx = (int)(m[r][c] - 'a');
    	if(n.child[charIdx] == null){
    		return;
    	}
    	m[r][c] = '-';
    	path.add(r * m.length + c);
    	int[] rowChg = {-1,1,0,0};
    	int[] colChg = {0,0,-1,1};
    	for(int i = 0; i < rowChg.length; i++){
    		int nextRow = r + rowChg[i];
    		int nextCol = c + colChg[i];
    		if(nextRow >= 0 && nextRow < m.length && nextCol >= 0 && nextCol < m[0].length && m[nextRow][nextCol] != '-'){
    			dfs(nextRow,nextCol,m,n.child[charIdx],wrdsAtCell,path);
    		}
    	}
    	m[r][c] = (char)(charIdx + 'a');
    	path.remove(path.size() - 1);
    }

  • 0

    @divyam01986
    What I am doing is creating an undirected graph (represented as an adjacency list) where words that share a cell in the matrix have an edge between one another.After this graph is created, we want to find words that have 1 or more edges to other words and remove their edges to their neighbors. After this removal, words that have an empty adjacency (don't share any cells with other words) will be included in the results list.


  • 0
    F

    @LHearen Are you interviewed onsite in US or China? Google ?


Log in to reply
 

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