listC++ Data Structure & Algorithm
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
จากข้อมูลที่โจทย์ให้มา
cpp
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 ออกมา โดยถ้าไม่มีให้คืนค่าว่างออกมา
จากข้อมูลที่โจทย์ให้มา
cpp
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 มา ที่มีทั้งคำและช่องว่าง จนหาขนาดตัวอักษรของ “คำสุดท้าย” ในประโยคที่ให้มา โดยไม่นับช่องว่าง
จากข้อมูลที่โจทย์ให้มา
cpp
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;
}
};