Pourquoi le fait de changer une ligne de mon code entraîne un débordement de pile ?

Question

Il s'agit d'un [problème de recherche d'union] : https://leetcode.com/problems/similar-string-groups/

Si je change la ligne parents[find(j)] = i; sur parents[find(i)] = j; le code entraînera un débordement de pile. Apparemment, le chemin est trop profond pour la méthode récursive find(). Mais je ne peux pas dire quelle différence fait ce changement. Quelqu'un peut-il m'aider ?

class Solution {
    int[] parents;
    public int numSimilarGroups(String[] A) {
        parents = new int[A.length];
        for(int i = 0;i < parents.length;i++) {
            parents[i] = i;
        }
        for(int i = 0;i < A.length;i++) {
            for(int j = 0;j < i;j++) {
                if(similar(A[i],A[j])) {
                    parents[find(j)] = i;
                }
            }
        }
        int ans = 0;
        for(int i = 0;i < parents.length;i++) {
            if(parents[i] == i)
                ans++;
        }
        return ans;
    }

    private int find(int curr) {
        int p = parents[curr];
        if(p != curr) {
            int pp = find(p);
            parents[curr] = pp;
        }
        return parents[curr];
    }

    private boolean similar(String a, String b) {
        int diff = 0;
        int i = 0;
        boolean consecutive = false;
        while(diff <= 2 && i < a.length()) {
            if(a.charAt(i) != b.charAt(i))
                diff++;
            if(i > 0 && a.charAt(i) == a.charAt(i-1))
                consecutive = true;
            i++;
        }
        return diff == 2 || diff == 0 && consecutive;
    }
}

Answer 1

Utilisation de parents[find(i)] = j permet à une valeur de devenir plus petite que son indice en répétant la valeur que les indices peuvent devenir. Cela peut aboutir à une situation où 2 éléments ont des index/valeurs inversés l'un par rapport à l'autre. Par exemple :

Étant donné que A.length == 5 votre tableau de départ sera le suivant :

parents[0] = 0 ; parents[1] = 1 ; parents[2] = 2 ; parents[3] = 3 ; parents[4] = 4 ;

Les valeurs que nous utiliserons seront les suivantes similar renvoyant à la vérité. En commençant par i = 2, j = 1 cela permettrait de passer les appels :

find(2);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[2]:
//          parents[0] = 0; parents[1] = 1; parents[2] = 1; parents[3] = 3; parents[4] = 4;

Suivant, i = 3, j = 1 :

find(3);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[3]:
//          parents[0] = 0; parents[1] = 1; parents[2] = 1; parents[3] = 1; parents[4] = 4;

Puis i = 3, j = 2 :

find(3); find(1);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[1]:
//          parents[0] = 0; parents[1] = 2; parents[2] = 1; parents[3] = 1; parents[4] = 4;

Vous pouvez voir maintenant que nous avons mis en place notre boucle infinie ( parents[1] = 2; parents[2] = 1 ). Si find est appelé avec 1 ou 2, il sera coincé entre ces deux valeurs. Nous avons besoin de deux étapes supplémentaires pour y arriver. i = 4, j = 1 :

find(4);    //Array doesn't change in recursive function

//Resulting array after applying j to parents[1]:
//          parents[0] = 0; parents[1] = 2; parents[2] = 1; parents[3] = 1; parents[4] = 1;

Enfin, i = 4, j = 2 :

find(4); find(1); find(2); find(1); find(2); find(1); find(2); ...

---

Utilisation de parents[find(j)] = i signifie que la valeur assignée ne peut pas devenir plus faible car i s'incrémente toujours alors que j se répète pour chaque itération de i . j peut être une valeur quelconque de 0 to i -1 .