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.