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

문제 설명:

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

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

예시 1:

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

예시 2:

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

예시 3:

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

제약:

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

초기 사고 과정:

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

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

기본 솔루션:

암호:

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), 배열을 제자리에서 수정하고 일정한 양의 추가 공간만 사용하기 때문입니다.

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

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

엣지 케이스 및 테스트:

엣지 케이스:

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

테스트 케이스:

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("   ")); // ""

일반적인 문제 해결 전략:

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

유사한 문제 식별:

1. 문자열 조작:

   • 특정 조건에 따라 문자열을 수정해야 하는 문제
   • 예: 문장의 각 단어에서 문자 순서를 바꾸는 경우

2. 2점슛 기법:

   • 두 개의 포인터를 사용하는 문제는 솔루션을 최적화하는 데 도움이 될 수 있습니다.
   • 예: 정렬된 배열에서 중복 항목 제거

3. 내부 알고리즘:

   • 제한된 추가 공간에서 작업을 수행해야 하는 문제
   • 예: 배열을 오른쪽으로 k만큼 회전

결론:

• 문자열에서 단어를 바꾸는 문제는 무차별 접근 방식과 최적화된 내부 접근 방식을 모두 사용하여 효율적으로 해결할 수 있습니다.
• 문제를 이해하고 관리 가능한 부분으로 나누는 것이 중요합니다.
• 명확한 논리를 사용하고 가독성을 최적화하면 솔루션을 쉽게 따라갈 수 있습니다.
• 다양한 엣지 케이스로 테스트하여 견고성을 보장합니다.
• 문제의 패턴을 인식하면 다른 문제에 유사한 솔루션을 적용하는 데 도움이 될 수 있습니다.

이러한 문제와 전략을 연습함으로써 문제 해결 능력을 향상시키고 다양한 코딩 과제에 더 잘 대비할 수 있습니다.

위 내용은 Typescript Coding Chronicles: 문자열의 역방향 단어의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!