สตริงไอโซมอร์ฟิก

แนวทางต่าง ๆ ในการแก้ไข Leetcode 205 ใน JavaScript

Isomorphic String เป็นปัญหาคลาสสิกที่ท้าทายให้เราพิจารณาว่าสตริงที่กำหนดสองสตริงมีการแมปอักขระแบบหนึ่งต่อหนึ่งหรือไม่ กล่าวอีกนัยหนึ่ง เราต้องตรวจสอบว่าเราสามารถแทนที่อักขระในสตริงหนึ่งด้วยอักขระที่เกี่ยวข้องจากสตริงอื่นในขณะที่รักษาลำดับไว้ได้หรือไม่

ในบทความนี้ เราจะสำรวจวิธีแก้ปัญหาที่มีประสิทธิภาพในการแก้ปัญหานี้ เราจะวิเคราะห์ความซับซ้อนด้านเวลาและพื้นที่ของโซลูชันของเรา ช่วยให้เราเข้าใจประสิทธิภาพและความสามารถในการปรับขนาดได้

คำชี้แจงปัญหา:

เมื่อระบุสองสตริง s และ t พิจารณาว่าเป็น isomorphic หรือไม่

สตริง s และ t สองสตริงเป็นแบบ isomorphic หากอักขระใน s สามารถแทนที่ได้เพื่อรับ t

อักขระที่ปรากฏทั้งหมดจะต้องถูกแทนที่ด้วยอักขระอื่นโดยยังคงรักษาลำดับของอักขระไว้ ห้ามอักขระสองตัวจับคู่กับอักขระตัวเดียวกัน แต่อักขระหนึ่งตัวอาจจับคู่กับตัวมันเองได้

วิธีที่ 1: การเปรียบเทียบดัชนี

1. เราวนซ้ำอักขระแต่ละตัวในสตริง s และ t และเปรียบเทียบดัชนีที่เกี่ยวข้องโดยใช้เมธอด indexOf
2. หากดัชนีของอักขระปัจจุบันไม่ตรงกัน เราจะส่งคืน false ซึ่งบ่งชี้ว่าสตริงนั้นไม่ใช่ isomorphic
3. หากการวนซ้ำเสร็จสิ้นโดยไม่พบความไม่สอดคล้องใดๆ เราจะส่งคืน true ซึ่งบ่งชี้ว่าสตริงเป็นแบบ isomorphic

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

ความซับซ้อนของเวลา:O(N²) โดยที่ N คือความยาวของสตริง s และ t

สำหรับอักขระแต่ละตัวใน s โค้ดจะใช้เมธอด indexOf เพื่อค้นหาอักขระถัดไปใน s และ t เมธอด indexOf มีความซับซ้อนของเวลาเป็น O(n) ในกรณีที่เลวร้ายที่สุด และการค้นหานี้จะดำเนินการสำหรับอักขระแต่ละตัวใน s

ความซับซ้อนของอวกาศ:O(1)

ไม่ใช้โครงสร้างข้อมูลเพิ่มเติมใดๆ ที่ปรับขนาดตามขนาดอินพุต ใช้พื้นที่คงที่ในการจัดเก็บตัวแปรและค่าชั่วคราวระหว่างการทำงานของฟังก์ชันเท่านั้น

วิธีที่ 2: การแมปอักขระ

1. รหัสใช้วัตถุ Map สองวัตถุเพื่อจัดเก็บการแมประหว่างอักขระใน s และ t
2. โดยวนซ้ำอักขระแต่ละตัวในสตริงและตรวจสอบว่าทั้งสองแผนที่ไม่มีการแมปสำหรับอักขระปัจจุบันหรือไม่
3. ถ้าไม่เช่นนั้น ระบบจะเพิ่มการแมประหว่างอักขระในทั้งสองแมป
4. หากแผนที่มีการแมปอยู่แล้ว จะตรวจสอบว่าการแมปที่มีอยู่ตรงกับอักขระปัจจุบันหรือไม่
5. หากไม่ตรงกัน สตริงจะไม่เป็นแบบ isomorphic และฟังก์ชันจะส่งกลับ false
6. หากการวนซ้ำเสร็จสิ้นโดยไม่พบความไม่สอดคล้องกันใดๆ สตริงจะถือเป็น isomorphic และฟังก์ชันจะส่งกลับ 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;
}

ความซับซ้อนของเวลา:O(N)

เรากำลังวนซ้ำอักขระแต่ละตัวในสตริง s และ t หนึ่งครั้ง โดยดำเนินการตามเวลาคงที่ภายในลูป ดังนั้นความซับซ้อนของเวลาจึงเป็นเส้นตรง

ความซับซ้อนของอวกาศ:O(1)

ความซับซ้อนของพื้นที่ถูกกำหนดโดยขนาดของแผนที่ sMap และ tMap ในกรณีที่เลวร้ายที่สุด อักขระทุกตัวใน s และ t จะไม่ซ้ำกัน ส่งผลให้แต่ละแมปมีรายการทั้งหมด 26 รายการ (สมมติว่าเป็นตัวอักษรภาษาอังกฤษตัวพิมพ์เล็ก) ดังนั้นความซับซ้อนของพื้นที่คือ O(1) เนื่องจากจำนวนรายการสูงสุดในแผนที่ได้รับการแก้ไขโดยไม่คำนึงถึงขนาดอินพุต

แนวทางที่ 3: การทำแผนที่ความถี่

1. เราใช้วัตถุความถี่สองตัว sFreq และ tFreq เพื่อติดตามดัชนีที่เห็นล่าสุดสำหรับอักขระแต่ละตัวในสตริง s และ t
2. โค้ดจะวนซ้ำอักขระในสตริงและตรวจสอบว่าดัชนีที่เห็นล่าสุดของอักขระปัจจุบันใน s ตรงกับดัชนีที่เห็นล่าสุดของอักขระที่เกี่ยวข้องใน t หรือไม่
3. หากไม่ตรงกัน สตริงจะไม่เป็นแบบ isomorphic และฟังก์ชันจะส่งกลับ false มิฉะนั้นจะอัพเดตออบเจ็กต์ความถี่ด้วยดัชนีปัจจุบัน

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

ความซับซ้อนของเวลา:O(N)

เราวนซ้ำอักขระของสตริงอินพุตทั้งสองหนึ่งครั้ง ดังนั้นความซับซ้อนของเวลาจึงเป็นเส้นตรง

ความซับซ้อนของอวกาศ:O(1)

ค่าคงที่ความซับซ้อนของพื้นที่เนื่องจากออบเจ็กต์ความถี่ sFreq และ tFreq มีขนาดคงที่สูงสุด 26 รายการ และไม่ขึ้นกับขนาดอินพุต

และคุณก็ได้แล้วทุกคน! เราได้สำรวจแนวทางที่แตกต่างกันสองแนวทาง เพิ่มประสิทธิภาพโซลูชันของเรา และหวังว่าจะได้รับความสนุกสนานไปตลอดทาง ฉันหวังว่าบทความนี้จะให้ข้อมูลเชิงลึกอันมีค่าแก่คุณและช่วยให้คุณเข้าใจแนวทางต่างๆ ในการแก้ปัญหานี้ได้ดียิ่งขึ้น ขอให้มีความสุขในการเขียนโค้ด!

ปัญหา - Leetcode 205