Go Java 알고리즘의 단어 패턴 문제를 해결하는 방법

Word 패턴

패턴 패턴과 문자열 s가 주어지면 s가 동일한 패턴을 따르는지 확인하세요.

여기서 "Follow"는 정확히 일치하는 것을 의미합니다. 예를 들어 패턴의 각 문자와 문자열 s의 비어 있지 않은 각 단어 사이에는 양방향 연결이 있습니다.

• 예 1:

입력: 패턴 = "abba", s = "dog cat cat dog"

출력: true

• 예 2:

입력: 패턴 = "abba", s = "dog cat cat fish"

출력: false

• 예 3:

입력: 패턴 = "aaaa", s = "dog cat cat dog"

출력: false

팁:

1 <= Pattern.length <= 300

pattern에는 영어 소문자만 포함됩니다.

1 <= s.length <= 3000

s에는 영어 소문자만 포함됩니다. 및 ''

s에는 선행 또는 후행 공백 쌍이 포함되지 않습니다.

s 각 단어는 단일 공백으로 구분됩니다.

방법 1: 해시 테이블(Java)

이 질문에서는 문자와 문자열을 판단해야 합니다. 그들 사이에 일대일 대응이 있는지 여부. 즉, 모든 문자는 고유한 문자열에 해당하고 모든 문자열은 단 하나의 문자에 해당합니다. 집합 이론에서는 이 관계를 "전단사"라고 합니다.

이 문제를 해결하기 위해 해시 테이블을 사용하여 각 문자에 해당하는 문자열과 각 문자열에 해당하는 문자를 기록할 수 있습니다. 그런 다음 각 문자와 문자열 쌍의 페어링 과정을 열거하고 지속적으로 해시 테이블을 업데이트합니다. 충돌이 발생하면 주어진 입력이 전단사 관계를 만족하지 않는다는 의미입니다.

질문은 본질적으로 str의 문자가 패턴의 문자와 일대일로 대응하는지 확인하도록 요구합니다.

즉, 패턴의 동일한 문자는 str에서도 동일해야 하며 다른 문자도 동일해야 합니다. be Different in str

사전, 즉 dict[x]=pattern.index(x)를 통해 패턴의 각 문자가 처음 나타나는 위치를 기록할 수 있습니다. 그런 다음 패턴의 각 문자를 탐색합니다.

i를 현재 탐색한 인덱스로 기억하세요.

그런 다음 dict[pattern[i]]는 패턴에 있는 문자 패턴[i]의 이전 인덱스입니다

str의 두 인덱스를 판단합니다. 해당 문자는 동일하고 그렇지 않으면 False를 반환

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch3str = new HashMap<Character, String>();
        int m = str.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); ++p) {
            char ch = pattern.charAt(p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str.charAt(j) != &#39; &#39;) {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch3str.containsKey(ch) && !tmp.equals(ch3str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch3str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }
}

시간 복잡도: O(n+m)

공간 복잡도: O(n+m)

방법 1: 해시 테이블(GO)

구체적인 방법 자세한 내용은 위에 명시되어 있습니다.

구체적인 방법:

pattern = "abba", 0110으로 변환

str = "dog cat cat dog", 0110

func wordPattern(pattern string, str string) bool {
    p := strings.Split(pattern,"")
    s := strings.Split(str," ")
    if len(p) != len(s) {
        return false
    }
    pNum,sNum := 0,0
    pString,sString := "",""
    pMap := map[string]int{}
    sMap := map[string]int{}
    for _,v := range p {
        if _,ok := pMap[v];ok{
            pString += strconv.Itoa(pMap[v])
        }else{
            pString += strconv.Itoa(pNum)
            pMap[v] = pNum
            pNum++
        }
    }
    for _,v := range s {
        if _,ok := sMap[v];ok{
            sString += strconv.Itoa(sMap[v])
        }else{
            sString += strconv.Itoa(sNum)
            sMap[v] = sNum
            sNum++
        }
    }
    if pString == sString {
        return true
    }
    return false
}

로 변환

시간 복잡도: O(n+m)

공간 복잡도: O(n+m)

위 내용은 Go Java 알고리즘의 단어 패턴 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!