Go Java アルゴリズムの単語パターン問題を解決する方法

単語のルール

パターン pattern と文字列 s が与えられた場合、s が同じルールに従うかどうかを判断します。

ここでの「フォロー」は完全一致を指します。たとえば、パターン内の各文字と文字列 s 内の空でない各単語の間には、双方向の接続対応ルールがあります。

• #例 1:

入力: pattern = "abba"、s = "dog cat cat Dog"

出力: true

• 例 2:

入力: pattern = "abba"、s = "dog cat catfish"

出力: false

• 例 3:

入力: pattern = "aaaa", s = "犬猫猫犬"

出力: false

プロンプト:

1 <= pattern.length < = 300

pattern 英小文字のみが含まれます

1

s 英小文字と ' '# のみが含まれます

## には先頭または末尾のスペースのペアは含まれません

各単語は 1 つのスペースで区切られます

方法 1: ハッシュ テーブル (Java)

この質問では、文字と文字列の間に正確な 1 対 1 の対応があるかどうかを判断する必要があります。つまり、任意の文字は一意の文字列に対応し、任意の文字列は 1 つの文字のみに対応します。集合論では、この関係は「全単射」と呼ばれます。

この問題を解決するには、ハッシュ テーブルを使用して、各文字に対応する文字列と、各文字列に対応する文字を記録します。次に、文字と文字列の各ペアのペアリングのプロセスを列挙し、ハッシュ テーブルを継続的に更新します。競合が発生した場合、それは指定された入力が全単射関係を満たしていないことを意味します。

この質問は基本的に、str 内の文字がパターン内の文字に 1 対 1 で対応するかどうかを判断することを求めています。

つまり、パターン内の同じ文字も同じである必要があります。 str の文字と異なる文字 str の文字も異なる必要があります

パターン内の各文字の最初の出現位置を辞書を通じて記録できます。つまり、dict[x]=pattern.index(x) 。次に、パターン内の各文字を走査します。

i を現在の走査のインデックスとして覚えておいてください。

その後、 dict[pattern[i]] は、次の文字 pattern[i] の前のインデックスです。 pattern

str の 2 つのインデックスに対応する文字が同じかどうかを判断し、異なる場合は 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)

Space複雑さ: 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 中国語 Web サイトの他の関連記事を参照してください。