1638. Count Substrings That Differ by One Character
https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
문제
이 문제를 이해하는데 어려움이 있었다. Example 1을 기준으로 설명을 하자면 다음과 같다.
"aba"에서 연속적인 순서로 문자열을 자르면 다음과 같다.
길이가 1일 때 => "a", "b", "a"
길이가 2일 때 => "ab", "ba"
길이가 3일 때 => "aba"
마찬가지로 "baba"를 연속적인 순서로 문자열을 자르면 다음과 같다.
길이가 1일 때 => "b", "a", "b", "a"
길이가 2일 때 => "ba", "ab", "ba"
길이가 3일 때 => "bab", "aba"
길이가 4일 때 => "baba"
가 된다. 이러한 문자열 조합에 길이 기준으로 서로 다른 문자차이가 1인 개수를 구하면 된다.
길이가 1일 때
"a" => "b"
"b" => "a"
"a" => "b" 서로 다른 문자 차이가 1인 것을 알 수 있다.
길이가 2일 때에는
"ab" => "ba" 에는 서로 다른 문자가 2인 것이고
"ab" => "ab" 에는 서로 다른 문자가 0인 것이다.
풀이(Brute Force)
모든 경우를 계산하기 위해선 중첩 for문을 사용해야 하고 길이 기준으로 subString 하기 위해서 gap이라는 길이를 나타내는 변수를 사용했다. 하지만 DP로 해결하는 방법으로는 감이 잡히지 않아 유튜브에 있는 보고 풀었다.
풀이(DP)
DP로 해결하는 방법은 의외로 간단했다. 예를 들어 문자열 "abc", "abd"가 있을 때
1. ("a", "a")가 같으니 1을 저장
2. ("b", "b")가 같으니 전 문자 ("a", "a") 저장된 값 + 1을 저장하면 2가 저장된다.
3. ("c", "d")가 다르니 전 문자("b", "b") 저장된 값 2를 가져온다. => ("bc", "bd"), ("abc", "abd")
4. ("c", "d")도 다르니 1을 더해준다. 2+1 => ("bc", "bd"), ("abc", "abd"), ("c", "d")
또한 문자열 "abca", "abda"가 있을 때
("abc", "abd")에 저장된 값 3을 리턴한다. => ("abc", "abd"), ("bca", "bda"), ("abca", "abda")
결과
느낀점
- 비슷한 문제가 나오면 풀기 힘들 것 같다. 계속해서 연습해야 겠다.
- 파이썬 이차원 배열 Sum할 때 numpy말곤 생각 안해봤는데 쉽게 할 수 있는 방법을 알게 되었다.
