Rumah >Java >javaTutorial >Bagaimana untuk menyelesaikan masalah corak perkataan dalam algoritma Go Java
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 SalahKerumitan 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) != ' ') { 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:
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!