สตริงย้อนกลับ

แนวทางต่าง ๆ ในการแก้ปัญหาด้วย JavaScript

คุณเคยพบว่าตัวเองจ้องมองที่เชือกและสงสัยว่าจะกลับลำดับของมันได้อย่างไร? วันนี้ เราจะสำรวจแนวทางต่างๆ มากมายที่เราสามารถใช้เพื่อแก้ปัญหานี้ รวมถึง ตัวชี้สองตัว หากคุณไม่คุ้นเคยกับตัวชี้สองตัว ไม่ต้องกังวล มันเป็นวิธีที่ชาญฉลาดในการจัดการกับอาร์เรย์ (และสตริง!) ที่เกี่ยวข้องกับการติดตามดัชนีสองตัวพร้อมกัน และไม่ต้องกังวล ฉันสัญญาว่าจะไม่อธิบายให้ตรงประเด็นจนเกินไป (ฉันทนไม่ไหวกับการเล่นสำนวน) เอนหลัง ผ่อนคลาย และดำดิ่งลงไปได้เลย!

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

เขียนฟังก์ชันที่กลับสตริง

วิธีที่ 1: กำลังดุร้าย

1. เราสามารถสร้างสตริงว่าง จากนั้นวนซ้ำผ่านสตริงอินพุตจากจุดสิ้นสุดไปยังจุดเริ่มต้น และเชื่อมอักขระแต่ละตัวเข้ากับสตริงใหม่

// ES6 Arrow Function
const reverseString = str => {
    let reversed = '';

    for(let i = str.length; i >= 0; i--) {
        reverseString += str[i];
    }

    return reverseString;
}

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

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

วิธีที่ 2: สองพอยน์เตอร์

1. เราสามารถใช้พอยน์เตอร์สองตัว ตัวหนึ่งเริ่มต้นจากจุดเริ่มต้นของสตริง และอีกตัวหนึ่งเริ่มต้นจากจุดสิ้นสุด
2. เราสลับอักขระในแต่ละดัชนีจนกว่าพอยน์เตอร์ทั้งสองจะมาบรรจบกันตรงกลาง
3. หมายเหตุ:องค์ประกอบที่แต่ละตัวชี้จะถูกสลับโดยใช้ การทำลายโครงสร้างอาร์เรย์

// ES6 Arrow Function
const reverseString = str => {
    let i = 0, j = str.length - 1;

    while(i <= j) {
        [str[i], str[j]] = [str[j], str[i]];
        i++;
        j--;
    }

    return str;
}

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

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

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

วิธีที่ 3: วิธีการในตัว

1. JavaScript มีเมธอดในตัวที่เรียกว่า reverse() ซึ่งสามารถใช้เพื่อย้อนกลับอาร์เรย์
2. เนื่องจากสตริงใน JavaScript สามารถปฏิบัติได้เหมือนกับอาร์เรย์ของอักขระ เราจึงสามารถแปลงสตริงเป็นอาร์เรย์ ย้อนกลับอาร์เรย์ แล้วแปลงกลับเป็นสตริงได้

// ES6 Arrow Function
const reverseString = str => {
    return str.split('').reverse().join('');
}

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

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

แนวทางที่ 4: การเรียกซ้ำ

เราสามารถย้อนกลับสตริงย่อยที่ไม่รวมอักขระตัวแรกแบบวนซ้ำ จากนั้นจึงต่ออักขระตัวแรกต่อท้าย

// ES6 Arrow Function
const reverseString = str => {
    if(str === '') return '';
    else return reverseString(str.substr(1)) + str.charAt(0);
}

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

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

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