CareerCup

Sorry about formatting

List<string> FindAllWords(char[,] mat, string filePath)
{
    bool[,] used = new bool[mat.length,mat.length];
    
    Trie t = new Trie(filePath);
    
    List<string> allWords = new List<string>();
    
    for(int i=0; i<mat.length ; i++)
     for(int j=0; j<mat.length; j++)
     {
         foreach(string str in FindWordsFromLocation(i,j,mat,used,t,""))
         {
             allWords.Add(str);
         }

     }
     
     return allWords ;
}

List<string> FindWordsFromLocation(int i, int j, char[,] mat, bool[,] used, Trie t, string prefix)
{
    if(i<0 || i>mat.length || j<0 || j>mat.length) return null;
    
    if(bool[i,j]==true) return null;
    
     
    List<string> words = new List<string>();
    
    if(t.ContainsWord(prefix))
    {
        words.Add(prefix);
    }
    
    string newPrefix = prefix + mat[i,j];
    used[i,j] = true;
    
    if(t.ContainsPrefix(newPrefix))
    {
        foreach(string str in FindWordsFromLocation(i+1,j,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i-1,j,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i,j+1,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i,j-1,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i+1,j+1,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i+1,j-1,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i-1,j+1,mat,used,t,newPrefix))
            words.Add(str);
        foreach(string str in FindWordsFromLocation(i-1,j-1,mat,used,t,newPrefix))
            words.Add(str);
    }
   
    used[i,j] = false;
    
    return words    
   
}

crab on the road

{ crab on the road
}

{ crab on the road
}

use trie tree to implement it