Skip to Content
CoursesCSC102การจับคู่รูปแบบด้วย Wildcard (Pattern Matching)

การจับคู่รูปแบบด้วย 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).

InputOutput
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"

  1. a ตรงกัน → เลื่อนทั้งคู่
  2. * เจอ → จดจำตำแหน่ง
  3. d ตรงกัน → จับคู่สำเร็จ

กรณี 2: s = "abc", p = "a?c"

  1. a ตรงกัน
  2. ? จับคู่กับ b
  3. c ตรงกัน

กรณี 3: s = "abc", p = "a*?"

  1. a ตรงกัน
  2. * จับคู่กับ b
  3. ? จับคู่กับ c
ปรับปรุงล่าสุด