알고리즘 문제 의 문자열 일치 문제

나 는 최근 에 어 려 운 정도 의 산법 문 제 를 복습 하여 많은 재 미 있 는 점 을 발견 했다.다른 사람의 해법 을 참고 한 후에 가장 간단 한 상황 에서 원래 의 문제 로 반추 하 는 것 은 자 물 쇠 를 풀 고 새로운 진 보 를 하 는 느낌 이라는 것 을 발견 했다.순환 에서 동태 적 인 계획 으로 사고 가 한 걸음 한 걸음 발전 하 는 것 은 마치 기복 이 있 는 소설 처럼 기록 되 어 제군 과 함께 감상 하 는 것 과 같다.
제목 은 다음 과 같다.

        s         p，          '.'   '*'         。

'.'         
'*'                
    ，            s ，        。

  :

s     ，      a-z      。
p     ，      a-z      ，     .   *。
   1:

  :
s = "aa"
p = "a"
  : false
  : "a"      "aa"      。
   2:

  :
s = "aa"
p = "a*"
  : true
  :    '*'                    ,            'a'。  ，    "aa"      'a'      。
   3:

  :
s = "ab"
p = ".*"
  : true
  : ".*"           （'*'）    （'.'）。
   4:

  :
s = "aab"
p = "c*a*b"
  : true
  :    '*'        ，   'c'   0  , 'a'      。          "aab"。
   5:

  :
s = "mississippi"
p = "mis*is*p*."
  : false

  ：  （LeetCode）

이것 은 문자열 이 일치 하 는 문제 입 니 다. 일치 하 는 문자열 에는 두 가지 특수 기호 인 '...' 와 '*' 가 들 어 있 을 수 있 습 니 다.
처음에 이 문 제 를 받 았 을 때 저 는 어 리 석 었 습 니 다. '*' 기 호 를 가 진 것 을 직접 분석 할 때 상황 에 따라 분석 하기 어렵 고 심지어 사고의 교착 상태 에 빠 졌 습 니 다.
문 제 를 간소화 할 수 있다 면 얼마나 좋 을 까? 그래, 우리 가 문 제 를 우리 가 이전에 했 던 문제 나 쉽게 할 수 있 는 문제 로 바 꾸 면 그 중에서 새로운 방향 을 발견 할 수 있 을 까?
질문 이 다음 과 같다 고 가정 합 니 다. 순수한 문자열 두 개가 일치 하도록 하 십시오.구현 코드 는 다음 과 같 습 니 다.

package main

func isMatch(text string, pattern string) bool {
    if pattern == "" {
        if text != "" {
            return false
        } else {
            return true
        }
    }
    first_match := false

    if pattern[0] == text[0] {
        first_match = true
    }

    return first_match && isMatch(text[1:], pattern[1:])
}

func main() {
    text := "abc"
    pattern := "ab"
    isMatch(text, pattern)
}

여기에 귀속 을 사 용 했 는데 이렇게 처리 한 것 은 후속 적 인 교 체 를 위 한 것 이다.그러면 조건 을 하나 더 추가 하면 '...' 기 호 를 추가 하고 '..' 기 호 를 가 진 문자열 이 문자열 과 일치 하면?
실현 할 때 첫 번 째 바이트 가 이 특수 기호 인지 아 닌 지 를 고려 해 야 한다.

func isMatch2(text string, pattern string) bool {
    if pattern == "" {
        if text != "" {
            return false
        } else {
            return true
        }
    }
    first_match := false

    if pattern[0] == text[0] || pattern[0] == '.' {
        first_match = true
    }
    return first_match && isMatch2(text[1:], pattern[1:])
}

'.' 기호의 상황 을 해결 할 수 있 고 '*' 기호의 상황 에 대해 우 리 는 더욱 생각 할 수 있다.가능성:

1. 0 회 매 칭.

2. 1 회 매 칭.구체 적 인 코드 는 다음 과 같다.

func isMatch(text string, pattern string) bool {
    if pattern == "" {
        if text != "" {
            return false
        } else {
            return true
        }
    }
    first_match := false
    
    text_bool := false
    if text != "" {
        text_bool = true
    }
    
    if text_bool && (pattern[0] == text[0] || pattern[0] == '.') {
        first_match = true
    }
    
    if len(pattern) >=2 && pattern[1] == '*' {
        return isMatch(text, pattern[2:]) || first_match && isMatch(text[1:], pattern)
    } else {
        return first_match && isMatch(text[1:], pattern[1:])
    }
}

이 코드 는 모두 재 귀적 으로 이 루어 졌 지만 재 귀적 인 시간 복잡 도 소모 가 더욱 크 고 매번 재 귀적 인 결 과 를 저장 하 는 것 을 고려 할 수 있 기 때문에 우 리 는 동적 계획 의 방향 으로 생각 할 수 있다.dp 저장 결 과 를 선택 하 십시오. dp [i] [j] 는 앞의 i 문자열 이 j 바이트 pattern 에 일치 하 는 결 과 를 표시 합 니 다.

func isMatch(s string, p string) bool {
    memory := make(map[string]bool)
    return dp(0, 0, memory, s, p)

}

func dp(i int, j int, memory map[string]bool, s string, p string) bool {
    iToStr := strconv.Itoa(i)
    jToStr := strconv.Itoa(j)
    keyStr := iToStr + "," + jToStr
    if _, ok := memory[keyStr]; ok {
        return memory[keyStr]
    }
    if j == len(p) {
        return i == len(s)
    }

    first := (i < len(s)) && (p[j] == s[i] || p[j] == '.')
    var ans bool
    if j <= (len(p) -2) && p[j+1] == '*' {
        ans = dp(i, j+2, memory,s, p) || first && dp(i+1, j, memory, s, p)
    } else {
        ans = first && dp(i+1, j+1, memory, s, p)
    }
    memory[keyStr] = ans
    return ans
}

반성: 더 좋 은 해법 이 있 을 까?예 를 들 어 순환 을 외부 에 두 는 것 이지 dp 함수 로 포장 하 는 것 이 아 닙 니까?