Interview technique : Une phrase palindrome LeetCode #125

Problème

Une phrase est un palindrome si :

• - après avoir converti toutes les lettres majuscules en lettres minuscules
• - et supprimé tous les caractères non alphanumériques

elle se lit de la même manière dans les deux sens. Les caractères alphanumériques comprennent les lettres et les chiffres.

Étant donné une chaîne s, renvoie true s'il s'agit d'un palindrome, ou false dans le cas contraire.

Explication

Selon l'énonné, si prend par exemple cette chaîne de caractère :

s = "A man, a plan, a canal: Panama"

et qu'on enlève les caractères non alphanumériques (qui ne sont pas les chiffres, ni des lettres alphabetiques), ici ce sont les, espaces, les virgules, les deux points. On obtient :

s = "amanaplanacanalpanama"

Cette nouvelle chaîne se lit exactement de la même façon la gauche vers la droite et de la droite vers la gauche.

L'énonncé veut un programme, qui prend n'importe qu'elle chaîne de caractère et vérifie si la chaîne peut se lire de la même façon de gauche à droite et de droite à gauche. Si oui on retourne true. Si non on retourne false.

Solution 1 : Technique de la force brute.

D'abord pour la première approche on va y aller avec à l'aveugle, la solution peut ne pas être optimal, mais juste pour la faire fonctionner et dans les prochaîne solution on va essayer d'améliorer.

Cette technique suppose que si la chaîne de caractère se lit de la même façon dans les 2 senses sa veut dire que :

• - si on renverse la chaîne de caractère, elle sera toujours egale à l'original.
• - on peut donc comparer la chaîne original et la chaîne renversé et retourner true si elle sont égales, et false si elles ne le sont pas.

class Solution{



    public static boolean isPalindrome(String s) {
        String s1 = s.toLowerCase(); 
        
        StringBuilder builder = new StringBuilder();
        
        for(int i=0; i!=s1.length(); i++){
            if(Character.isLetter(s1.charAt(i))){
                builder.append(s1.charAt(i));
            }


            if(Character.isDigit(s1.charAt(i))){
                builder.append(s1.charAt(i));
            }
        }


        String s2 = builder.toString();
        String s3 = builder.reverse().toString();
        
        if(s2.equals(s3)){
            return true;
        }
        return false;
    }


    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s));
    }
}

Solution 2

Solution 3