8
votes

Trouver une chaîne dans un tableau 2 dimensions

Il s'agit d'une question d'entrevue qui doit être optimisée pour le temps.

Supposons que vous ayez une matrice 2 dimensions et que vous avez une chaîne dise "Amazon" à l'intérieur de la matrice de sorte que les caractères individuels puissent être présents de gauche à droite, à droite à gauche, de haut en bas et de descendre.

Je vais expliquer avec l'exemple: xxx

La matrice ci-dessus a deux chaînes d'Amazonie. Vous devez retourner le nombre de ces chaînes présentes.

algorithm time-complexity

6 commentaires

Trouvez le premier personnage et recherchez les caractères suivants avec la direction

Est-il autorisé à utiliser la même position deux fois dans une chaîne? par exemple. Le mazon compterait-il comme une occurrence? (Commencez à gauche à gauche, puis à droite)

Si le futur tableau était {N, O, Z, O, N, A}, l'algorithme retournera-t-il 3 ou 2?

@Anothergeek: Je pense que vous voulez dire nozome qu'il ne devrait être 3.

De votre question, il n'est pas clair si la chaîne doit être dans une seule direction et que les enveloppements peuvent être utilisés.

Je n'ai jamais pensé à l'enveloppe et je n'ai pas dit non plus. Je dirais d'abord tenter la chose sans courrier.

6 Réponses :

1
votes

Vous pouvez exécuter un BFS de chaque cellule de la matrice ayant 'A' et compter le nombre de voies d'Amazon peut être construit. Enfin les ajouter tous.

bords: Un nœud adjacent (haut, bas, gauche, à droite) (cellule) a un bord dirigé du nœud actuel (cellule) s'il contient le caractère suivant d'Amazon. Juste exemple, tous les nœud adjacents ayant 'n' ont un bord dirigé du nœud ayant 'O'.

0 commentaires

1
votes

Vous n'avez donné qu'un seul exemple. Si:

Tous les caractères "remplissants" sont toujours quelque chose qui n'est pas dans la chaîne
La chaîne est toujours complète et non divisée
la chaîne a au moins une lettre non répétée
Ensuite, il vous suffit de compter combien il y a de lettres non répétées. Par exemple, avec 'Amazon', il vous suffit de compter le nombre de 'Z' (ou 'M', ou 'O' ou 'N') sont dans le tableau.
Ce n'est pas aussi général qu'un chemin de recherche d'algorithme, mais certainement plus rapide.

1 commentaires

Les caractères de remplissage peuvent être n'importe quoi. La chaîne peut être n'importe quoi.

1
votes

itérer sur matrice = O (n ^ 2)
Trouvez la première occurrence de la touche [0] Ie 'A' in Amazon et rangez-la dans [I, J]
Démarrer à partir de matrice [I, J] et essayez de suivre "Amazon" en utilisant les quatre directions
a. Vous pouvez utiliser bfs ou dfs
b. Si trouvé, augmentez le nombre de 1
c. Si non trouvé, continuez
Complexité du temps = O (N ^ 2 + N) {Utilisation de DFS}

0 commentaires

1
votes

Fabriquez une table tridimensionnelle où chaque position dans la matrice fait référence à une matrice représentant chaque lettre de l'alphabet. Effectuer deux itérations à la fois de haut de haut, de gauche à droite et à droite à gauche, rangée à la ligne: si la chaîne existe, vous rencontrerez sa première ou dernière lettre (la seule façon de rencontrer une lettre moyenne est si vous avez déjà vu la première ou la dernière partie de son match connecté). Agrégez vos résultats de gauche, mais comprenez la position de l'élément ci-dessous à l'index représentant le prochain caractère possible avec la longueur et la direction actuelles. Si une correspondance de table est rencontrée, convertissez-la en une correspondance complète ou partielle (chacune de ces lettres + cellule de position peut contenir plus d'une correspondance potentielle).

0 commentaires

2
votes

J'ai fait un simple BFS, chaque fois que le premier caractère de la chaîne toofind (dans votre cas Amazon) correspond à un caractère dans la matrice 2D. Un tableau 2D visité simple est utilisé pour vérifier les caractères marqués dans une itération:

public class FindStrings {

private static int count = 0;       // Final Count

public static void find(Character[][] a, String toFind) {

    int rows = a.length;
    int col = a[0].length;

    boolean[][] visited = new boolean[a.length][a[0].length];

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < col; j++) {
            if (a[i][j] == toFind.charAt(0)) {
                findUtil(visited, a, i, j, 0, toFind, new StringBuilder(), rows - 1, col - 1,new ArrayList<String>());
                visited[i][j] = false;
            }
        }
    }

}

private static void findUtil(boolean[][] visited, Character[][] a, int i, int j, int index, String toFind, StringBuilder result, int R, int C,ArrayList<String> list) {

    result.append(a[i][j]);
    //This list just prints the entire Path
    list.add(i+"-"+j);
    if (index == toFind.length() - 1 && result.toString().equals(toFind)) {
        System.out.println(list.toString());
        count++;
        return;
    }
    visited[i][j] = true; // Just to mark the character so that one character is not visited twice for a string match
    int nextIndex = index + 1; //Next index of the String to be compared

    int nextR, nextC;

    //Down
    if (i + 1 >= 0 && j >= 0 && i + 1 <= R && j <= C && !visited[i + 1][j] && a[i + 1][j] == toFind.charAt(nextIndex)) {
        nextR = i + 1;
        nextC = j;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        //Every time we are done with the next character in the 2D Array we mark it visited
        visited[nextR][nextC] = false;
    }
    //Right
    if (i >= 0 && j + 1 >= 0 && i <= R && j + 1 <= C && !visited[i][j + 1] && a[i][j + 1] == toFind.charAt(nextIndex)) {
        nextR = i;
        nextC = j + 1;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        visited[nextR][nextC] = false;
    }
    //Left
    if (i >= 0 && j - 1 >= 0 && i <= R && j - 1 <= C && !visited[i][j - 1] && a[i][j - 1] == toFind.charAt(nextIndex)) {
        nextR = i;
        nextC = j - 1;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        visited[nextR][nextC] = false;
    }
    //Up
    if (i - 1 >= 0 && j >= 0 && i - 1 <= R && j <= C && !visited[i - 1][j] && a[i - 1][j] == toFind.charAt(nextIndex)) {
        nextR = i - 1;
        nextC = j;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        visited[nextR][nextC] = false;
    }


}

public static int getCount() {
    return count;
}

public static void main(String[] args) {

    Character[][] a = new Character[][]{
            {'B', 'B', 'A', 'B', 'B', 'N'},
            {'B', 'B', 'M', 'B', 'B', 'O'},
            {'B', 'B', 'A', 'B', 'B', 'Z'},
            {'B', 'O', 'Z', 'O', 'N', 'A'},
            {'B', 'B', 'O', 'Z', 'B', 'M'},
            {'B', 'B', 'N', 'A', 'M', 'A'}
    };

    String toFind = "AMAZON";

    find(a, toFind);
    System.out.println(getCount());

}

0 commentaires

0
votes

J'ai écrit un code Java qui résolvez cette question

mais c'est une solution coûteuse en termes de complexité de temps

comme je traverse la numérisation du tableau 2D pour 'A' puis de cet élément i Traverse Dans 4 directions, balayage pour M puis a et ainsi sur

donc le pire des cas si nous supposons qu'une numérisation de la matrice est n ^ 2 et la longueur du mot que nous balayons est k

sera

O (n ^ 2 * k ^ 4) le 4 ici est pour les 4 directions que nous devons rechercher < / p>

Voici la classe complète de la classe xxx

}

0 commentaires