Pendekatan berbeda untuk menyelesaikan Leetcode 205 di JavaScript

String Isomorfik adalah masalah klasik yang menantang kita untuk menentukan apakah dua string tertentu memiliki pemetaan karakter satu-ke-satu. Dengan kata lain, kita perlu memeriksa apakah kita dapat mengganti karakter dalam satu string dengan karakter yang sesuai dari string lainnya sambil menjaga urutannya.

Pada artikel ini, kita akan mencari solusi efektif untuk mengatasi masalah ini. Kami akan menganalisis kompleksitas waktu dan ruang dari solusi kami, sehingga memungkinkan kami memahami efisiensi dan skalabilitasnya.

Pernyataan Masalah:

Diberikan dua string s dan t, tentukan apakah keduanya isomorfik.

Dua string s dan t bersifat isomorfik jika karakter di s dapat diganti menjadi t.

Semua kemunculan suatu karakter harus diganti dengan karakter lain dengan tetap menjaga urutan karakter. Tidak ada dua karakter yang dapat dipetakan ke karakter yang sama, namun satu karakter dapat dipetakan ke dirinya sendiri.

Pendekatan 1: Perbandingan Indeks

  1. Kami mengulangi setiap karakter dalam string s dan t dan membandingkan indeks terkait menggunakan metode indexOf.
  2. Jika indeks karakter saat ini tidak cocok, kami mengembalikan false, yang menunjukkan bahwa string tersebut tidak isomorfik.
  3. Jika perulangan selesai tanpa menemukan ketidakkonsistenan apa pun, kami mengembalikan true, yang menunjukkan bahwa string tersebut isomorfik.
// ES6 Arrow Function
const isIsomorphic = (s, t) => {
    if(s.length !== t.length) return false;

    for(let i = 0; i < s.length; i++) {
        if(s.indexOf(s[i]) !== t.indexOf(t[i])) {
            return false;
        }
    }

    return true;
}

Kompleksitas Waktu:O(N²), dengan N adalah panjang string s dan t.

Untuk setiap karakter di s, kode menggunakan metode indexOf untuk mencari kemunculan karakter berikutnya di s dan t. Metode indexOf memiliki kompleksitas waktu O(n) dalam kasus terburuk, dan pencarian ini dilakukan untuk setiap karakter di s.

Kompleksitas Ruang:O(1)

Itu tidak menggunakan struktur data tambahan apa pun yang berskala dengan ukuran input. Ia hanya menggunakan sejumlah ruang yang konstan untuk menyimpan variabel dan nilai sementara selama eksekusi fungsi.

Pendekatan 2: Pemetaan Karakter

  1. Kode ini menggunakan dua objek Map, untuk menyimpan pemetaan antar karakter di s dan t.
  2. Ini mengulangi setiap karakter dalam string dan memeriksa apakah kedua peta tidak berisi pemetaan untuk karakter saat ini.
  3. Jika tidak, ini akan menambahkan pemetaan antar karakter ke kedua peta.
  4. Jika peta sudah berisi pemetaan, ia akan memeriksa apakah pemetaan yang ada cocok dengan karakter saat ini.
  5. Jika tidak cocok, stringnya tidak isomorfik, dan fungsinya mengembalikan false.
  6. Jika perulangan selesai tanpa menemukan ketidakkonsistenan, string dianggap isomorfik, dan fungsinya mengembalikan true.
// ES6 Arrow Function
const isIsomorphic = (s, t) => {
    if(s.length !== t.length) return false;

    const sMap = new Map();
    const tMap = new Map();

    for(let i = 0; i < s.length; i++) {
        const charS = s[i];
        const charT = t[i];

        if(!sMap.has(charS) && !tMap.has(charT)) {
            sMap.set(charS, charT);
            tMap.set(charT, charS);
        } else {
            if(sMap.get(charS) !== charT || tMap.get(charT) !== charS) {
                return false;
            }
        }
    }

    return true;
}

Kompleksitas Waktu:O(N)

Kami mengulangi setiap karakter dalam string s dan t satu kali, melakukan operasi waktu konstan dalam loop. Oleh karena itu, kompleksitas waktu bersifat linier.

Kompleksitas Ruang:O(1)

Kompleksitas ruang ditentukan oleh ukuran peta sMap dan tMap. Dalam kasus terburuk, semua karakter di s dan t adalah unik, sehingga menghasilkan total 26 entri di setiap peta (dengan asumsi huruf kecil dalam bahasa Inggris). Oleh karena itu, kompleksitas ruang adalah O(1), karena jumlah maksimum entri dalam peta adalah tetap berapa pun ukuran masukannya.

Pendekatan 3: Pemetaan Frekuensi

  1. Kami menggunakan dua objek frekuensi sFreq dan tFreq untuk melacak indeks yang terakhir terlihat untuk setiap karakter dalam string s dan t.
  2. Kode mengulangi karakter dalam string dan memeriksa apakah indeks yang terakhir terlihat dari karakter saat ini di s cocok dengan indeks yang terakhir terlihat dari karakter terkait di t.
  3. Jika tidak cocok, stringnya tidak isomorfik, dan fungsinya mengembalikan false. Jika tidak, ia akan memperbarui objek frekuensi dengan indeks saat ini.
// ES6 Arrow Function
const isIsomorphic = (s, t) => {
    if(s.length !== t.length) return false;

    let sFreq = {}, tFreq = {};

    for(let i = 0; i < s.length; i++) {
        const charS = s[i];
        const charT = t[i];

        if(sFreq[charS] !== tFreq[charT]) return false;

        sFreq[charS] = i + 1;
        tFreq[charT] = i + 1;
    }

    return true;
}

Kompleksitas Waktu:O(N)

Kami mengulangi karakter dari kedua string masukan satu kali. Oleh karena itu, kompleksitas waktu bersifat linier.

Kompleksitas Ruang:O(1)

Kompleksitas ruang konstan karena objek frekuensi sFreq dan tFreq memiliki ukuran tetap paling banyak 26 entri dan tidak bergantung pada ukuran input.

Dan begitulah teman-teman! Kami telah mengeksplorasi dua pendekatan berbeda, mengoptimalkan solusi kami, dan semoga dapat bersenang-senang selama prosesnya. Saya harap artikel ini memberi Anda wawasan berharga dan membantu Anda lebih memahami berbagai pendekatan untuk memecahkan masalah ini. Selamat membuat kode!

Masalah - Leetcode 205