[자료구조] String (문자열)

String (문자열)

문자열은 문자들의 집합, 배열로서 엄밀하게 자료 구조라고 할 수 없지만 배열과 유사하기 때문에 자료 구조의 하위 항목으로 묶었다.

문자열을 검색하기 위한 일반적인 자료 구조는 다음과 같이 있다.

• Trie/Prefix Tree
• Suffix Tree

그리고 문자열 관련 알고리즘은 다음과 같이 있다.

• Rabin Karp for efficient searching of substring using a rolling hash
• KMP for efficient searching of substring

시간 복잡도

문자열은 배열과 유사하기 때문에 시간 복잡도 또한 같다.

동작	Big-O
접근	O(1)
검색	O(n)
삽입	O(n)
삭제	O(n)

다른 문자열과 관련된 작업

동작	Big-O	비고
부분 문자열 찾기	O(n.m)	이는 일반 적인 시간 복잡도이며, 더 효율적인 알고리즘이 존재한다. https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
문자열 연결	O(n + m)
문자열 자르기	O(m)
문자열 분리	O(n + m)
양 끝 공백 제거	O(n)

기법

문자 세기

문자열에서 특정 문자의 개수를 셀 때는 보통 hash table이나 map을 사용한다. 만약 언어에서 문자를 검색하는 함수를 내장하고 있다면 그것을 사용하자

아나그램 (Anagram)

아나그램은 원래의 모든 글자중 하나씩만 사용하여 새로운 단어나 구를 만드는 놀이이다.

두 문자열이 아나그램인지 확인하는 방법은 다음과 같이 있다.

• 두 문자열을 모두 정렬하고, 정렬 결과가 같은지 확인한다. O(n.log(n))의 시간 복잡도를 가진다.
• 각 문자를 소수에 대응 시키고, 그 숫자들을 모두 곱했을 때 아나그램은 같은 배수를 가져야 한다. (소인수 분해) O(n)의 시간 복잡도를 가진다.
• 각 문자가 등장한 개수를 확인한다. O(n)의 시간 복잡도를 가진다.

Palindrome

Palindrome은 앞으로 읽어도, 뒤로 읽어도 거꾸로해도 같은 문자열인 단어를 말한다.

문자열이 Palindrome인지 확인하는 방법은 다음과 같이 있다.

• 문자열을 뒤집고 같은지 확인해 본다.
• 투 포인터를 사용하여 하나는 앞에서 부터, 하나는 뒤에서 부터 시작하여 같은지 확인한다.

필수 문제

• LeetCode
  • Valid Anagram
  • Valid Palindrome
  • Longest Substring Without Repeating Characters

추천 연습 문제

• LeetCode
  • Longest Repeating Character Replacement
  • Find All Anagrams in a String
  • Minimum Window Substring
  • Group Anagrams
  • Longest Palindromic Substring

참조

Array cheatsheet for coding interviews | Tech Interview Handbook