Typescript Coding Chronicles: 문자열의 역방향 단어-JS 튜토리얼-php.cn

Typescript Coding Chronicles: 문자열의 역방향 단어

PHPz

풀어 주다： 2024-07-18 18:03:28

원래의

583명이 탐색했습니다.

Typescript Coding Chronicles: Reverse Words in a String

문제 설명:

입력 문자열 s가 주어지면 단어 순서를 반대로 바꿉니다. 단어는 공백이 아닌 일련의 문자로 정의됩니다. s 안의 단어는 최소한 하나의 공백으로 구분됩니다. 단일 공백으로 연결된 단어의 문자열을 역순으로 반환합니다.

s에는 선행 또는 후행 공백이 포함될 수 있으며 두 단어 사이에 여러 공백이 포함될 수 있습니다. 반환된 문자열에는 단어를 구분하는 공백 하나만 있어야 합니다. 추가 공백을 포함하지 마세요.

예시 1:

입력: s = "하늘은 파랗다"
출력: "blue is sky the"

예시 2:

입력: s = " hello world "
출력: "world hello"
설명: 역방향 문자열에는 선행 또는 후행 공백이 포함되어서는 안 됩니다.

예시 3:

입력: s = "좋은 예"
출력: "예제 a"
설명: 두 단어 사이의 여러 공백을 역순 문자열에서 단일 공백으로 줄여야 합니다.

제약:

1
s에는 영문자(대문자, 소문자), 숫자, 공백 ''이 포함됩니다.
s에 단어가 하나 이상 있습니다.

초기 사고 과정:

이 문제를 해결하려면 다음을 수행해야 합니다.

문자열을 단어로 나눕니다.
단어 순서를 반대로 바꿔 보세요.
각 단어 사이에 하나의 공백을 두고 다시 단어를 결합합니다.

기본 솔루션:

암호:

function reverseWordsBruteForce(s: string): string {
    // Split the string by spaces and filter out empty strings
    let words = s.trim().split(/\s+/);

    // Reverse the array of words
    words.reverse();

    // Join the words with a single space
    return words.join(' ');
}

로그인 후 복사

시간 복잡도 분석:

시간 복잡도: O(n), 여기서 n은 문자열의 길이입니다. 분할, 반전, 결합에는 모두 선형 시간이 걸립니다.
공간 복잡도: O(n), 여기서 n은 문자열의 길이입니다. 단어를 배열에 저장하고 최종 결과를 문자열에 저장합니다.

제한사항:

이 솔루션은 제약 조건을 고려할 때 효율적입니다. 그러나 단어 배열을 위해 추가 공간을 사용합니다.

최적화된 솔루션:

문자열 데이터 유형이 변경 가능하고 O(1) 추가 공간을 사용하여 해당 위치에서 해결해야 하는 경우 2포인터 기술을 사용하여 원래 문자열 내의 단어를 뒤집을 수 있습니다.

암호:

function reverseWordsOptimized(s: string): string {
    // Trim the string and convert it to an array of characters
    let chars = s.trim().split('');

    // Helper function to reverse a portion of the array in place
    function reverse(arr: string[], left: number, right: number) {
        while (left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }

    // Reverse the entire array of characters
    reverse(chars, 0, chars.length - 1);

    // Reverse each word in the reversed array
    let start = 0;
    for (let end = 0; end <= chars.length; end++) {
        if (end === chars.length || chars[end] === ' ') {
            reverse(chars, start, end - 1);
            start = end + 1;
        }
    }

    // Join the characters back into a string and split by spaces to remove extra spaces
    return chars.join('').split(/\s+/).join(' ');
}

로그인 후 복사

시간 복잡도 분석:

시간 복잡도: O(n), 여기서 n은 문자열의 길이입니다. 각 문자는 일정한 횟수만큼 처리됩니다.
공간 복잡성: O(1), 배열을 제자리에서 수정하고 일정한 양의 추가 공간만 사용하기 때문입니다.

기본 솔루션에 비해 개선된 사항:

최적화된 솔루션은 문자 배열에 대해 내부 연산을 수행하여 공간 복잡성을 줄입니다.

엣지 케이스 및 테스트:

엣지 케이스:

문자열에는 앞뒤 공백이 포함되어 있습니다.
문자열에 단어 사이에 공백이 여러 개 포함되어 있습니다.
문자열에 단어가 하나만 포함되어 있습니다.
문자열 길이가 최소 또는 최대 제한에 있습니다.

테스트 케이스:

console.log(reverseWordsBruteForce("the sky is blue")); // "blue is sky the"
console.log(reverseWordsBruteForce("  hello world  ")); // "world hello"
console.log(reverseWordsBruteForce("a good   example")); // "example good a"
console.log(reverseWordsBruteForce("singleWord")); // "singleWord"
console.log(reverseWordsBruteForce("   ")); // ""

console.log(reverseWordsOptimized("the sky is blue")); // "blue is sky the"
console.log(reverseWordsOptimized("  hello world  ")); // "world hello"
console.log(reverseWordsOptimized("a good   example")); // "example good a"
console.log(reverseWordsOptimized("singleWord")); // "singleWord"
console.log(reverseWordsOptimized("   ")); // ""

로그인 후 복사

일반적인 문제 해결 전략:

문제 이해: 문제 설명을 주의 깊게 읽고 요구 사항과 제약 조건을 이해하세요.
주요 작업 식별: 단어 분할, 반전, 결합 등 필요한 주요 작업을 결정합니다.
가독성 최적화: 명확하고 간결한 논리를 사용하여 코드를 쉽게 따라갈 수 있도록 합니다.
철저한 테스트: 엣지 케이스를 포함한 다양한 케이스로 솔루션을 테스트하여 정확성을 확인하세요.

유사한 문제 식별:

문자열 조작:
- 특정 조건에 따라 문자열을 수정해야 하는 문제
- 예: 문장의 각 단어에서 문자 순서를 바꾸는 경우
2점슛 기법:
- 두 개의 포인터를 사용하는 문제는 솔루션을 최적화하는 데 도움이 될 수 있습니다.
- 예: 정렬된 배열에서 중복 항목 제거
내부 알고리즘:
- 제한된 추가 공간에서 작업을 수행해야 하는 문제
- 예: 배열을 오른쪽으로 k만큼 회전