Tout d'abord, bonne question. L'examinateur veut voir comment vous abordez le problème. Dans ce genre de problèmes, vous devez analyser le problème et choisir soigneusement une structure de données.
Dans ce cas, deux structures de données me viennent à l'esprit : HashMaps et Tries . HashMaps ne conviennent pas, car vous n'avez pas de clé complète à rechercher (vous pouvez utiliser un index inversé basé sur des cartes, mais vous avez dit avoir déjà trouvé ces solutions). Vous n'avez que les parties - c'est là que la solution Trie est le meilleur ajustement.
Ainsi, l'idée avec les essais est que vous pouvez ignorer les branches de caractères qui ne sont pas dans votre dictionnaire tout en parcourant l'arbre.
Dans votre cas, l'arbre ressemble à ceci (j'ai laissé de côté les ramifications pour les chemins non ramifiés) :
\*
a
bacus
d
deltoid
g
a
gaff
i
giraffe
m
microphone
r
reef
q
qar
Ainsi, à chaque niveau de ce tri, nous examinons les enfants du nœud actuel et vérifions si le caractère de l'enfant figure dans notre dictionnaire.
Si oui, nous allons plus loin dans cet arbre et supprimons le caractère de l'enfant de notre dictionnaire.
Cela continue jusqu'à ce que vous atteigniez une feuille (plus d'enfants), ici vous savez que ce mot contient tous les caractères de ce dictionnaire. C'est un candidat possible. Maintenant, nous voulons retourner dans l'arbre jusqu'à ce que nous trouvions une autre correspondance que nous pouvons comparer. Si la dernière correspondance trouvée est plus petite, jetez-la, si elle est plus longue, c'est notre meilleur candidat possible.
Un jour, la récusion se terminera et vous obtiendrez le résultat souhaité.
Notez que cela fonctionne s'il n'y a qu'un seul mot le plus long, sinon vous devriez renvoyer une liste de candidats (c'est la partie inconnue de l'entretien où vous devez demander ce que l'interviewer veut voir comme solution).
Vous avez donc eu besoin du code Java, le voici avec un simplissime Trie et la version du mot le plus long :
public class LongestWord {
class TrieNode {
char value;
List<TrieNode> children = new ArrayList<>();
String word;
public TrieNode() {
}
public TrieNode(char val) {
this.value = val;
}
public void add(char[] array) {
add(array, 0);
}
public void add(char[] array, int offset) {
for (TrieNode child : children) {
if (child.value == array[offset]) {
child.add(array, offset + 1);
return;
}
}
TrieNode trieNode = new TrieNode(array[offset]);
children.add(trieNode);
if (offset < array.length - 1) {
trieNode.add(array, offset + 1);
} else {
trieNode.word = new String(array);
}
}
}
private TrieNode root = new TrieNode();
public LongestWord() {
List<String> asList = Arrays.asList("abacus", "deltoid", "gaff", "giraffe",
"microphone", "reef", "qar");
for (String word : asList) {
root.add(word.toCharArray());
}
}
public String search(char[] cs) {
return visit(root, cs);
}
public String visit(TrieNode n, char[] allowedCharacters) {
String bestMatch = null;
if (n.children.isEmpty()) {
// base case, leaf of the trie, use as a candidate
bestMatch = n.word;
}
for (TrieNode child : n.children) {
if (contains(allowedCharacters, child.value)) {
// remove this child's value and descent into the trie
String result = visit(child, remove(allowedCharacters, child.value));
// if the result wasn't null, check length and set
if (bestMatch == null || result != null
&& bestMatch.length() < result.length()) {
bestMatch = result;
}
}
}
// always return the best known match thus far
return bestMatch;
}
private char[] remove(char[] allowedCharacters, char value) {
char[] newDict = new char[allowedCharacters.length - 1];
int index = 0;
for (char x : allowedCharacters) {
if (x != value) {
newDict[index++] = x;
} else {
// we removed the first hit, now copy the rest
break;
}
}
System.arraycopy(allowedCharacters, index + 1, newDict, index,
allowedCharacters.length - (index + 1));
return newDict;
}
private boolean contains(char[] allowedCharacters, char value) {
for (char x : allowedCharacters) {
if (value == x) {
return true;
}
}
return false;
}
public static void main(String[] args) {
LongestWord lw = new LongestWord();
String longestWord = lw.search(new char[] { 'a', 'e', 'f', 'f', 'g', 'i',
'r', 'q' });
// yields giraffe
System.out.println(longestWord);
}
}
Je ne peux également que suggérer la lecture du livre Cracking the Coding Interview : 150 questions et solutions sur la programmation Il vous guide dans la prise de décision et la construction de ces algorithmes spécialisés sur les questions d'entretien.
