JavaScript에서 반복되지 않는 하위 문자열을 찾는 방법

실제 개발에서는 문자열에 대해 일부 작업과 처리를 수행해야 하는 경우가 많습니다. 그 중 하나는 반복되지 않는 하위 문자열을 찾는 것입니다. 예를 들어, 문자열 "abcabcbb"에서 가장 긴 비반복 하위 문자열은 "abc"이고 문자열 "bbbbbb"에서 가장 긴 비반복 하위 문자열은 "b"입니다. 이러한 문제는 알고리즘에서 "가장 길고 반복되지 않는 부분 문자열" 문제로 알려져 있으며 JavaScript를 사용하여 해결할 수 있습니다.

1. 폭력적인 열거 방법

가장 간단한 방법은 무차별 열거 방법을 사용하는 것입니다. 즉, 각 문자에 대해 문자열을 처음부터 순회하고 반복되는 문자가 나타날 때까지 하위 문자열에 반복되지 않는 문자를 하나씩 추가하는 것입니다. . 그런 다음 이때 부분 문자열의 길이를 기록하고 부분 문자열을 재설정한 다음 순회가 끝날 때까지 문자열을 아래쪽으로 계속 순회합니다.

코드는 다음과 같습니다.

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;
}

이 방법의 시간 복잡도는 O(n^3)입니다. 중첩 루프 수가 매우 많기 때문에 긴 문자열을 처리할 때 효율성이 매우 비효율적입니다.

2. 슬라이딩 윈도우 방식

효율성을 높이기 위해 슬라이딩 윈도우 방식을 사용할 수 있습니다. 슬라이딩 윈도우의 아이디어는 길이 k의 윈도우를 유지하고 이 윈도우를 슬라이드하여 문자열을 처리하는 것입니다. 이 문제에서 슬라이딩 윈도우의 길이는 반복되지 않는 문자열의 길이입니다.

구체적으로 문자열을 탐색할 때 시작 포인터와 끝 포인터를 정의하고 이 두 포인터가 창을 형성합니다. 각 루프에서 끝 포인터가 가리키는 요소가 창에 존재하지 않으면 이를 창에 추가한 다음 창을 확장하고 창 길이를 업데이트할 수 있습니다. 끝 포인터가 가리키는 요소가 창에 이미 존재하는 경우 시작 포인터를 오른쪽으로 이동하고 끝 포인터가 가리키는 요소가 창에 더 이상 존재하지 않을 때까지 창을 축소해야 합니다. 이 과정에서 매핑 테이블을 사용하여 창의 각 요소가 나타나는 횟수를 기록해야 합니다.

코드는 다음과 같습니다.

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;
}

슬라이딩 윈도우 방법의 시간 복잡도는 O(n)입니다. HashMap을 사용하여 문자를 빠르게 찾고 저장하는데, 이는 무차별 열거 방법보다 더 빠르고 효율적입니다.

3. 요약

문자열에서 가장 길고 반복되지 않는 부분 문자열 문제의 경우 무차별 열거 방법과 슬라이딩 윈도우 방법이라는 두 가지 방법을 사용하여 해결할 수 있습니다. 무차별 열거 방법은 시간 복잡도가 높은 반면 슬라이딩 윈도우 방법은 더 효율적입니다. 실제 개발에서는 필요에 따라 문제를 해결하기 위한 적절한 방법을 선택할 수 있습니다.

위 내용은 JavaScript에서 반복되지 않는 하위 문자열을 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!