การจับคู่รูปแบบด้วย Wildcard (Pattern Matching)
โจทย์
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ? and * where:
?Matches any single character.*Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
| Input | Output |
|---|---|
| aa a | false |
| aa ?a | true |
โค้ด
import java.util.Scanner;
public class Program {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
String p = scanner.nextLine();
int sLen = s.length();
int pLen = p.length();
int sPointer = 0, pPointer = 0;
int starIndex = -1, sTempIndex = -1;
while (sPointer < sLen) {
if (pPointer < pLen && (p.charAt(pPointer) == '?' || p.charAt(pPointer) == s.charAt(sPointer))) {
sPointer++;
pPointer++;
}
else if (pPointer < pLen && p.charAt(pPointer) == '*') {
starIndex = pPointer;
sTempIndex = sPointer;
pPointer++;
}
else if (starIndex != -1) {
pPointer = starIndex + 1;
sTempIndex++;
sPointer = sTempIndex;
}
else {
System.out.println(false);
return;
}
}
while (pPointer < pLen && p.charAt(pPointer) == '*') {
pPointer++;
}
boolean result = pPointer == pLen;
System.out.println(result);
}
}คำอธิบาย
1. การประกาศตัวแปร
int sLen = s.length(); // ความยาวของสตริงอินพุต
int pLen = p.length(); // ความยาวของรูปแบบ
int sPointer = 0, pPointer = 0; // ตัวชี้ตำแหน่งปัจจุบัน
int starIndex = -1, sTempIndex = -1; // ตัวชี้ตำแหน่ง * และตำแหน่งที่จับคู่2. การจับคู่แบบปกติหรือ ?
if (pPointer < pLen && (p.charAt(pPointer) == '?' || p.charAt(pPointer) == s.charAt(sPointer))) {
sPointer++;
pPointer++;
}- ตรงกันแบบปกติ หรือเจอ
?ให้เลื่อนตัวชี้ทั้งสองไปข้างหน้า
3. การจับคู่กับ *
else if (pPointer < pLen && p.charAt(pPointer) == '*') {
starIndex = pPointer; // จดจำตำแหน่ง *
sTempIndex = sPointer; // จดจำตำแหน่งในสตริง
pPointer++; // เลื่อนไปดูตัวถัดไปในรูปแบบ
}4. การย้อนกลับเมื่อจับคู่ไม่สำเร็จ
else if (starIndex != -1) {
pPointer = starIndex + 1; // กลับไปที่ตำแหน่งหลัง *
sTempIndex++; // ลองจับคู่ * กับตัวอักษรถัดไป
sPointer = sTempIndex;
}5. การตรวจสอบ * ที่เหลือ
while (pPointer < pLen && p.charAt(pPointer) == '*') {
pPointer++;
}แผนภาพการทำงาน
ตัวอย่างการทำงาน
กรณี 1: s = "acd", p = "a*d"
aตรงกัน → เลื่อนทั้งคู่*เจอ → จดจำตำแหน่งdตรงกัน → จับคู่สำเร็จ
กรณี 2: s = "abc", p = "a?c"
aตรงกัน?จับคู่กับbcตรงกัน
กรณี 3: s = "abc", p = "a*?"
aตรงกัน*จับคู่กับb?จับคู่กับc
ปรับปรุงล่าสุด