Bagaimana untuk menyelesaikan masalah corak perkataan dalam algoritma Go Java

Corak perkataan

Diberi corak corak dan rentetan s, tentukan sama ada s mengikut corak yang sama.

Ikuti di sini merujuk pada padanan tepat Contohnya, terdapat sambungan dua arah antara setiap huruf dalam corak dan setiap perkataan bukan kosong dalam rentetan s.

• Contoh 1:

Input: pattern = "abba", s = "dog cat cat dog"

Output: benar

• Contoh 2:

Input: pattern = "abba", s = "dog ikan kucing kucing"

Output: palsu

• Contoh 3:

Input: corak = "aaaa", s = "anjing kucing kucing anjing"

Output: palsu

Petunjuk:

1 <= corak.panjang < = 300

corak hanya mengandungi huruf kecil Inggeris

1 <= s.length <= 3000

s hanya mengandungi huruf kecil Inggeris dan ' '

Dalam soalan ini, kita perlu menentukan sama ada terdapat korespondensi satu dengan satu yang tepat antara aksara dan rentetan. Iaitu, mana-mana aksara sepadan dengan rentetan unik, dan sebarang rentetan sepadan dengan hanya satu aksara. Dalam teori set, hubungan ini dipanggil "bijection".

Untuk menyelesaikan masalah ini, kita boleh menggunakan jadual cincang untuk merekod rentetan yang sepadan dengan setiap aksara dan aksara yang sepadan dengan setiap rentetan. Kemudian kami menghitung proses berpasangan setiap pasangan aksara dan rentetan dan mengemas kini jadual cincang secara berterusan Jika konflik berlaku, ini bermakna input yang diberikan tidak memenuhi perhubungan bijection.

Soalan pada dasarnya meminta kita untuk menentukan sama ada watak dalam str sepadan dengan watak dalam corak satu-satu

Dalam erti kata lain, watak yang sama dalam corak juga harus sama dalam str, dan aksara yang berbeza Aksara dalam str juga harus berbeza

Kita boleh merekodkan kedudukan kejadian pertama bagi setiap aksara dalam corak melalui kamus, iaitu dict[x]=pattern.index(x). Kemudian kita melintasi setiap huruf dalam corak,

, ingat i sebagai indeks traversal semasa,

, kemudian dict[pattern[i]] ialah indeks sebelumnya bagi corak aksara[ i] dalam corak

Tentukan sama ada huruf yang sepadan dengan dua indeks dalam str adalah sama Jika ia berbeza, kembalikan Salah

Kerumitan masa: O(n+. m)

ruang Kerumitan: O(n+m)

Kaedah 1: Jadual cincang (GO)

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;
    }
}

Idea kaedah khusus telah diterangkan di atas, sila lihat di atas kandungan untuk butiran

Kaedah khusus:

corak = "abba", ditukar kepada 0110

str = "anjing kucing kucing anjing", ditukar kepada 0110

Kerumitan masa: O(n+m)

Kerumitan ruang: O(n+m)

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah corak perkataan dalam algoritma Go Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!