Accueil › Coding & algorithmique › Les problèmes de chaînes qui tombent vraiment
Les problèmes de chaînes qui tombent vraiment
Les chaînes de caractèresdebutant
Cinq problèmes reviennent dans presque tous les entretiens Java. Les connaître libère l'esprit pour la discussion qui suit.
1. Inverser les mots d'une phrase
static String inverserMots(String s) {
String[] mots = s.strip().split("\\s+");
Collections.reverse(Arrays.asList(mots));
return String.join(" ", mots);
}
2. Compression basique — avec la règle qu'on oublie :
static String compresser(String s) {
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
int n = 0;
while (i < s.length() && s.charAt(i) == c) { i++; n++; }
sb.append(c).append(n);
}
return sb.length() < s.length() ? sb.toString() : s; // ← la règle oubliée
}
3. Rotation — l'astuce en une ligne :
static boolean estRotation(String a, String b) {
return a.length() == b.length() && (a + a).contains(b);
}
4. Chaînes isomorphes — deux Maps, pas une :
static boolean isomorphes(String a, String b) {
if (a.length() != b.length()) return false;
Map<Character, Character> ab = new HashMap<>(), ba = new HashMap<>();
for (int i = 0; i < a.length(); i++) {
char x = a.charAt(i), y = b.charAt(i);
if (ab.putIfAbsent(x, y) != null && ab.get(x) != y) return false;
if (ba.putIfAbsent(y, x) != null && ba.get(y) != x) return false;
}
return true;
}
5. Caractère intrus — XOR, O(1) en espace :
static char intrus(String a, String b) { // b = a mélangée + 1 caractère
int x = 0;
for (char c : a.toCharArray()) x ^= c;
for (char c : b.toCharArray()) x ^= c;
return (char) x;
}
Les termes à connaître
- Compression de chaîne
Remplacer les répétitions par un compte : « aaabbc » → « a3b2c1 ». On renvoie l'original si la compression ne gagne rien — la règle qu'on oublie.
- Rotation
« erbonjou » est une rotation de « bonjour »… ou pas. L'astuce :
best une rotation deasi et seulement sia.length() == b.length()et(a + a).contains(b).- Inverser les mots
« le chat dort » → « dort chat le ». Se résout avec
split+ inversion, ou en place sur unchar[]pour un O(1) en espace.- Chaîne isomorphe
Deux chaînes où chaque caractère de l'une correspond à un unique caractère de l'autre, de façon cohérente et bijective. Se vérifie avec deux Maps.
- Caractère manquant
Trouver ce qui différencie deux chaînes presque identiques : comptage, ou XOR de tous les caractères — l'astuce en O(1) en espace.
- Normalisation
Ramener l'entrée à une forme comparable avant de traiter : casse, accents, espaces. À décider explicitement avec l'examinateur.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.