실제 개발에서는 문자열에 대해 일부 작업과 처리를 수행해야 하는 경우가 많습니다. 그 중 하나는 반복되지 않는 하위 문자열을 찾는 것입니다. 예를 들어, 문자열 "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 중국어 웹사이트의 기타 관련 기사를 참조하세요!