Aller au menu - Aller au contenu
KACEM Portfolio
Vous êtes ici : Kacem Portfolio >> Code Source >> Java >> Les anagrammes

Les anagrammes

Définition :
Dans ce programme, 2 chaines sont anagrammes si elles sont formées exactement des mêmes caractères. Par exemple aube et beau sont anagrammes.

But du code :
Créer une méthode qui teste si 2 chaines passées en paramètres sont anagrammes ou pas. Elle doit retourner true si c'est le cas et false si non.

Algorithme 1 : Tri et comparaison
On commence par trier les 2 chaines de caractères par ordre alphabétique, ensuite il suffit de comparer le résultat pour savoir si elles sont anagrammes ou pas.
Par exemple :
-> portfolio et folioport
Après le tri :
-> filoooprt

Ici je vais utiliser le tri par insertion, mais le plus rapide est je pense le QSort ;)
Sans plus tarder voici le code :
Code java:
public static boolean anagramme(String s1, String s2)
{
        if(s1.length() != s2.length())
                return false;
        else
        {
                if(!signature(s1).equalsIgnoreCase(signature(s2)))
                        return false;
        }
                return true;
}

public static String signature(String s) {
        int l = s.length();
        StringBuffer sb = new StringBuffer(s);
       
        for(int i=0; i<l; i++)
        {
                char elementAInserer = sb.charAt(i);
                for(int j=0; j<i; j++)
                {
                        char elementCourant = sb.charAt(j);
                        if(elementAInserer < elementCourant)
                        {
                                sb.insert(j, elementAInserer);
                                sb.deleteCharAt(j+1);
                                elementAInserer = elementCourant;
                        }
                        sb.insert(i, elementAInserer);
                        sb.deleteCharAt(i+1);
                }
        }
        return sb.toString();
}

Algorithme 2 : Supprimer les doublons
C'est simple, je parcours la première chaine et je supprime la première occurrence de chaque caractère dans la 2ème ...
Ici je l'ai fais avec 2 boucles imbriquées, mais il est possible de le réduire à une seule boucle. Je mettrai à jour le code dès que je l'aurais finis ;)
Code java:
public static boolean anagramme(String s1, String s2) {
        if(s1.length() != s2.length())
                return false;
        else
        {
                StringBuffer sb1= new StringBuffer(s1);
                StringBuffer sb2= new StringBuffer(s2);
                int l=sb1.length();
               
                for(int i=0; i<l; i++)
                {
                        for(int j=0; j<l; j++)
                        {
                                if(sb1.charAt(i)==sb2.charAt(j))
                                {
                                        sb2.deleteCharAt(j);
                                        sb1.deleteCharAt(i);
                                        j+=l;
                                        l--;
                                        i--;
                                }
                        }
                }
                if(sb1.length()!=0 || sb2.length()!=0)
                        return false;
        }
        return true;
}

Il y a d'autres méthodes plus rapides, je les mettrai ici dès que je trouverai la solution

Par k@cem, le 22/11/2008 18:11.