문자열 부분 수열 판별: 단순 풀이부터 대용량 최적화까지
문제 정의
두 개의 문자열 source와 target이 주어질 때, source가 target의 부분 수열(subsequence)인지 판별하라. 두 문자열은 모두 소문자 알파벳으로 구성된다.
부분 수열은 원본 문자열에서 일부 문자를 제거하되(0개도 가능), 남은 문자의 상대적 순서를 유지하여 만들 수 있는 문자열이다. 예를 들어 "ace"는 "abcde"의 부분 수열이지만 "aec"는 아니다.
확장 시나 ...
7월 30일 14:13에 게시됨
문자열 동적 계획법: 부분 수열 카운팅, 삭제 연산, 그리고 편집 거리 최적화
1. 서로 다른 부분 수열의 개수 구하기
두 개의 문자열 text와 pattern이 주어졌을 때, text의 부분 수열 중 pattern과 일치하는 경우의 수를 계산하는 문제입니다. 부분 수열이란 원본 문자열에서 문자의 상대적 순서를 유지한 채 일부 문자를 제거하여 만들 수 있는 새로운 문자열을 의미합니다. 결과값은 32비트 부호 있는 정수 범위를 보장합니다.
class Solution {
pu ...
6월 16일 02:33에 게시됨