알고리즘 요약(10) - 패턴 일치 문제

문자열 변환, 귀속 등 여러 가지 상황

205. Isomorphic Strings

제목 주소

https://leetcode.com/problems/isomorphic-strings/

제목 설명

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example, Given “egg”, “add”, return true.
Given “foo”, “bar”, return false.
Given “paper”, “title”, return true.
Note: You may assume both s and t have the same length.

ac 코드

문자열로 변환

class Solution {
public:

    string _pattern(string s)
    {
        int len = s.size();
        string pattern = "";
        map<char, int> mp;
        int index = 1;
        for (int i = 0; i < len; i++)
        {
            char c1 = s[i];
            if (mp[c1] == 0)
            {
                mp[c1] = index;
                pattern += ('0' + index);
                index++;
            }
            else{
                int in = mp[c1];
                pattern += ('0' + in);
            }
        }
        return pattern;
    }

    bool isIsomorphic(string s, string t) {

        string p1 = _pattern(s);
        string p2 = _pattern(t);
        return p1 == p2;
    }
};

290. Word Pattern

제목 주소

https://leetcode.com/problems/word-pattern/

10. 재귀성 해결되지 않음

제목 주소

https://leetcode.com/problems/regular-expression-matching/

제목 설명

Implement regular expression matching with support for ‘.’ and ‘*’

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

ac

주요한 문제, 예를 들면 aaab, a*b와 일치하는 몇 가지 문제는 귀속구해를 채택한다

/*
    . 
    star    
*/
bool isMatch(char* s, char* p) {
    if (s == NULL || p == NULL || *p == '*')
        return false;
    if (*p == '\0')
        return *s == '\0';

    if (*(p + 1) != '*') // *
    {
        if (*s == '\0')
            return false;
        if (*p != '.' && *p != *s)
            return false;
        return isMatch(s + 1, p + 1); //  
    }
    else{
        int slen = strlen(s);
        if (isMatch(s, p + 2))
            return true;
        for (int i = 0; i < slen; ++i)
        {
            if (*p != '.' && *p != *(s + i))
                return false;
            if (isMatch(s + i + 1, p + 2))
                return true;
        }
        return false;
    }
}