Comment trouver des sous-chaînes non répétitives en JavaScript

Dans le développement réel, nous devons souvent effectuer certaines opérations et traitements sur les chaînes, dont l'une consiste à trouver des sous-chaînes non répétitives. Par exemple, dans la chaîne « abcabcbb », la sous-chaîne non répétitive la plus longue est « abc », et dans la chaîne « bbbbbb », la sous-chaîne non répétitive la plus longue est « b ». Ces problèmes sont connus dans les algorithmes sous le nom de problème de « sous-chaîne non répétitive la plus longue », et nous pouvons les résoudre en utilisant JavaScript.

1. Méthode d'énumération violente

La méthode la plus simple consiste à utiliser la méthode d'énumération par force brute, c'est-à-dire à parcourir la chaîne à partir de zéro pour chaque caractère et à ajouter des caractères non répétitifs à la sous-chaîne un par un jusqu'à ce qu'une répétition soit rencontrée. Ensuite, enregistrez la longueur de la sous-chaîne à ce moment, réinitialisez la sous-chaîne et continuez à parcourir la chaîne vers le bas jusqu'à la fin du parcours.

Le code est le suivant :

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  for(let i = 0; i < str.length; i++) {
    let map = new Map(); // 定义 Map 来保存子串中元素出现的次数
    let length = 0; // 定义子串长度为 0
    for(let j = i; j < str.length; j++) {
      if(map.has(str[j])) { // 如果子串中已经有这个元素了
        maxLength = Math.max(maxLength, length); // 更新最大长度
        break; // 说明这个子串已经不符合要求了，跳出内部循环
      } else {
        map.set(str[j], 1); // 在 Map 中记录该元素的出现次数
        length++; // 子串长度 +1
        maxLength = Math.max(maxLength, length); // 更新最大长度
      }
    }
  }
  return maxLength;
}

La complexité temporelle de cette méthode est O(n^3). Étant donné que le nombre de boucles imbriquées est très grand, son efficacité est très inefficace lors du traitement de chaînes plus longues.

2. Méthode de la fenêtre coulissante

Afin d'améliorer l'efficacité, nous pouvons utiliser la méthode de la fenêtre coulissante. L'idée de la fenêtre coulissante est de maintenir une fenêtre de longueur k et de faire glisser cette fenêtre pour traiter les chaînes. Dans ce problème, la longueur de la fenêtre glissante est la longueur de la chaîne non répétitive.

Plus précisément, lors du parcours d'une chaîne, nous définissons un pointeur de début et un pointeur de fin, et ces deux pointeurs formeront une fenêtre. Dans chaque boucle, si l'élément pointé par le pointeur de fin n'existe pas dans la fenêtre, on peut l'ajouter à la fenêtre, puis agrandir la fenêtre et mettre à jour la longueur de la fenêtre. Si l'élément pointé par le pointeur de fin existe déjà dans la fenêtre, nous devons déplacer le pointeur de début vers la droite et réduire la fenêtre jusqu'à ce que l'élément pointé par le pointeur de fin n'existe plus dans la fenêtre. Dans ce processus, nous devons utiliser une table de mappage pour enregistrer le nombre d'occurrences de chaque élément dans la fenêtre.

Le code est le suivant :

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  let map = new Map(); // 定义 Map 来保存元素出现的次数
  let left = 0; // 定义左指针为 0
  for(let right = 0; right < str.length; right++) {
    if(map.has(str[right])) { // 如果窗口内已经有该元素了
      left = Math.max(left, map.get(str[right]) + 1); // 更新左指针，向右移动
    }
    map.set(str[right], right); // 在 Map 中记录该元素的位置
    maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
  }
  return maxLength;
}

La complexité temporelle de la méthode de fenêtre coulissante est O(n). Elle utilise HashMap pour localiser et stocker rapidement les caractères, ce qui est plus rapide et plus efficace que la méthode d'énumération par force brute.

3. Résumé

Pour le problème de sous-chaîne non répétitive le plus long dans une chaîne, nous pouvons utiliser deux méthodes pour le résoudre : la méthode d'énumération par force brute et la méthode de fenêtre glissante. La méthode d'énumération par force brute a une complexité temporelle élevée, tandis que la méthode de la fenêtre glissante est plus efficace. Dans le développement réel, nous pouvons choisir la méthode appropriée pour résoudre le problème selon nos besoins.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!