String Problem

โจทย์ที่ 5: Roman to Integer

โจทย์ https://leetcode.com/problems/roman-to-integer

อธิบายโจทย์แบบสั้นๆ มีตัวอักษร Roman มาให้ จงแปลงตัวอักษร Roman เป็นตัวเลข ตามกฎในตารางด้านล่างนี้

กฎการแปลงเลข Roman แบบสั้นๆ

• ถ้าตัวอักษรมีค่าเท่ากันหรือน้อยกว่า จะทำการบวกต่อกันเสมอ เช่น III = 3, VII = 7, XXI = 21
• ถ้าตัวอักษรเจอว่าตัวอักษรต่อไปมีค่ามากกว่า จะเป็นการ “ลบเลข” ออกจากตัวอักษร Roman ตัวต่อไป เช่น IV = 4, XL = 40, XLI = 41 (กฎนี้จะเป็นจริงกับตัวอักษรต่อไปที่ติดกันเท่านั้น)
• การรันตีว่าจะไม่มีการเขียนผิดกฎเลข Roman

จากข้อมูลที่โจทย์ให้มา

Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

จาก Testcase ที่ให้มาได้อธิบายให้เห็นชัดเจนว่าหากเราแยกส่วนออกมาจะมีการบวกเลขยังไงบ้าง

จากปัญหานี้ Idea ที่ต้องทำแน่ๆคือ

• Loop ไปยังทุกตัวอักษรใน String แต่ละตัว
• แต่ละตัวอักษรจะต้องตรวจสอบด้วยว่า ตัวอักษรตัวต่อไปมีมากกว่าหรือไม่ ซึ่งถ้ามากกว่าแปลว่า ตัวอักษรปัจจุบันจะต้องลบค่าแทนที่จะบวกค่าเข้าไป เช่น IV ที่มีค่าเท่ากับ 4
  • ตอนเจอ I (1) ก่อน เราก็จะเช็คว่า ตัวต่อไป คือ V (5) เจอว่ามีค่ามากกว่า I ที่เป็นตัวปัจจุบัน ดังนั้น เราจึงทำการ -1 ค่าปัจจุบันก่อน
  • และพอเจอ V ก็จะพบว่า ไม่มีตัวอักษรต่อไป ดังนั้นจึงบวกค่าเข้าไปได้ปกติ ก็จะสามารถออกมาเป็น -1 + 5 = 4 ออกมาได้

Solution

class Solution {
public:
  // สร้าง function สำหรับแปลงตัวอักษร Romanji
  int romanValue(char r) {
    switch (r) {
    case 'I':
      return 1;
    case 'V':
      return 5;
    case 'X':
      return 10;
    case 'L':
      return 50;
    case 'C':
      return 100;
    case 'D':
      return 500;
    case 'M':
      return 1000;
    }
    return -1; // ถ้าไม่เข้าเคสไหนเลยให้ return -1 เป็น fallback ไป
  }

  int romanToInt(string s) {
    int total = 0;
    for (int i = 0; i < s.length(); i++) {
      // ดึงค่า Roman ตัวปัจจุบัน
      int current = romanValue(s[i]);
		  // ดึงค่า Roman ตัวถัดไป (หากตัวถัดไปเป็นตัวสุดท้ายแล้วให้เป็นค่า 0 = ก็จะมากกว่าเสมอได้)
      int next = (i + 1 < s.length()) ? romanValue(s[i + 1]) : 0;

      // เช็คว่า ถ้าค่าตัวปัจจุบัน น้อยกว่า ค่าตัวถัดไป = ต้องลบออก
      if (current < next) {
        total -= current;
      } else {
      // แต่ถ้าไม่ใช่ให้บวกตามปกติเข้าไป
        total += current;
      }
    }
    return total;
  }
};

โจทย์ที่ 6: Longest Common Prefix

โจทย์ https://leetcode.com/problems/longest-common-prefix/description/

อธิบายโจทย์แบบสั้นๆ มี Array ของ String จงหา “ตัวอักษรนำหน้า” ที่เหมือนกันของทุก String ใน Array ออกมา โดยถ้าไม่มีให้คืนค่าว่างออกมา

จากข้อมูลที่โจทย์ให้มา

Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

จาก Testcase

• ตัวอย่างแรก จะเห็นว่า String ทั้ง 3 ตัวขึ้นต้นด้วย “fl” เหมือนกัน ดังนั้นจึงคืน “fl” เป็นคำตอบออกมา
• แต่ตัวอย่างที่ 2 ไม่มีตัวอักษรนำหน้าร่วมกันเลย จึงได้ค่าว่างออกมา

จากปัญหานี้ Idea คือ

• ต้องวน loop string แน่ๆ
• และต้องวน loop string ไป array ไปพร้อมๆกันทุกตำแหน่ง จนกว่าจะเจอข้อความที่ไม่เหมือนกันและส่งคำตอบออกมา

Solution

class Solution {
public:
  string longestCommonPrefix(vector<string> &strs) {
    if (strs.empty())
      return ""; 

    // กำหนด string prefix เริ่มต้น
    string prefix = "";
  
    // ทำการ loop ไปยังทุกตัวของ string ตัวแรกสุด
    for (int idx = 0; idx < strs[0].length(); idx++) {
      // ดึง character ตำแหน่งตาม index ที่กำลังวน loop
      char c = strs[0][idx]; 

      // ทำการวน loop ไปยังทุก string ที่อยู่ใน array เพื่อเทียบตัวอักษรในตำแหน่งเดียวกัน
      for (int i = 1; i < strs.size(); i++) { 
        // หากเจอว่า index นั้นเกินขนาดของ String ที่กำลังวนอยู่ หรือ String มีตัวที่ไม่เหมือนกัน
        // สามารถตอบได้ทันทีด้วยตัวแปร prefix (เนื่องจากเราจะไม่สามารถเจอตัวที่เหมือนกันได้อีกแล้ว)
        if (idx >= strs[i].length() || strs[i][idx] != c) {
          return prefix; // Return คำตอบออกไป
        }
      }
      prefix += c; // ถ้าไม่มีปัญหาอะไร ทุกตัวเหมือนกันหมด ค่อยๆต่อ character เข้าไป
    }
    return prefix;// เมื่อวนครบหมด ส่ง prefix ออกไปเป็นคำตอบ
  }
};

โจทย์ที่ 7: Length of Last Word

โจทย์ https://leetcode.com/problems/length-of-last-word/

อธิบายโจทย์แบบสั้นๆ ให้ String n มา ที่มีทั้งคำและช่องว่าง จนหาขนาดตัวอักษรของ “คำสุดท้าย” ในประโยคที่ให้มา โดยไม่นับช่องว่าง

จากข้อมูลที่โจทย์ให้มา

Example 1:
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:
Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:
Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

จาก Test case

• ตัวอย่างแรก ก็ตรงไปตรงมา คำสุดท้ายคือ World ที่มีขนาด 5 ตัวอักษร คำตอบจึงเป็น 5 ออกมา
• ตัวอย่างที่ 2 คำสุดท้ายเป็น moon แต่อย่างที่เห็นมันมีช่องว่างอยู่ เราต้องไม่นับช่องว่างเหล่านั้นและแสดงออกมาแค่ 4

จากปัญหานี้ Idea คือ

• loop string รายตัวตรวจสอบ
• เราสนใจแค่ตัวสุดท้าย ให้เริ่ม loop string จาก index สุดท้ายแทน (ขนาดของ string)
• ทำการมองข้ามช่องว่าง และเริ่มนับจากตัวอักษรไปจนถึงช่องว่างของอีกฝั่งออกมาแทน

มองเป็นภาพ ไอเดียจะเป็นประมาณนี้

Solution

class Solution {
public:
  int lengthOfLastWord(string s) {
    int length = 0; // เก็บตัวแปรสำหรับนับขนาดของตัวอักษร
    int i = s.length() - 1; // เริ่มต้น index จากตำแหน่งท้ายสุด

    // เลื่อนจากตำแหน่งท้ายสุดมาตาม space ที่เว้นอยู่
    while (i >= 0 && s[i] == ' ') {
      i--;
    }

    // เลื่อนต่อไปจนถึงจุดที่เจอว่าไม่เป็นตัวอักษร (เจอว่าเป็น space)
    // ทุกครั้งที่เลื่อนไปให้นับตัวอักษรเพิ่มใน length
    while (i >= 0 && s[i] != ' ') {
      length++;
      i--;
    }

    // ส่งคำตอบเป็น length ออกไป
    return length;
  }
};