การตรวจสอบ Subsequence ของสตริง

โจทย์

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).

Input:

• Shorter string s
• Longer string t

Output:

• True if s is a subsequence of t, false otherwise

โค้ด

import java.util.Scanner;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        String s = scanner.nextLine();
        String t = scanner.nextLine();
 
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
 
        System.out.println(i == s.length());
    }
}

คำอธิบาย

1. การประกาศคลาสและรับข้อมูล

import java.util.Scanner;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        String s = scanner.nextLine(); // สตริงที่ต้องการตรวจสอบ
        String t = scanner.nextLine(); // สตริงต้นฉบับ

• ใช้ Scanner รับสตริงสองตัว
• s คือสตริงที่ต้องการตรวจสอบว่าเป็น subsequence หรือไม่
• t คือสตริงต้นฉบับที่ยาวกว่า

2. การตรวจสอบ Subsequence ด้วย Two Pointers

int i = 0, j = 0;  // ตัวชี้ตำแหน่งในสตริง s และ t
while (i < s.length() && j < t.length()) {
    if (s.charAt(i) == t.charAt(j)) {
        i++;    // เลื่อนตัวชี้ i เมื่อพบตัวอักษรที่ตรงกัน
    }
    j++;        // เลื่อนตัวชี้ j ทุกครั้ง
}

• ใช้เทคนิค Two Pointers:
• i ชี้ตำแหน่งในสตริง s
• j ชี้ตำแหน่งในสตริง t
• วนลูปตราบใดที่ยังไม่ถึงจุดสิ้นสุดของทั้งสองสตริง
• เมื่อพบตัวอักษรที่ตรงกัน เลื่อน i ไปตำแหน่งถัดไป
• เลื่อน j ไปตำแหน่งถัดไปทุกครั้ง

3. การตรวจสอบผลลัพธ์และแสดงผล

System.out.println(i == s.length());

• ถ้า i เท่ากับความยาวของ s แสดงว่าพบตัวอักษรครบทุกตัวใน s
• ถ้า i ไม่เท่ากับความยาวของ s แสดงว่าพบตัวอักษรไม่ครบ

แผนภาพการทำงาน

ตัวอย่างการทำงาน

ตัวอย่างที่ 1

s = "ace"
t = "abcde"

การทำงาน:

1. i=0, j=0: ‘a’ == ‘a’ ✓ (i=1, j=1)
2. i=1, j=1: ‘c’ ≠ ‘b’ ✗ (j=2)
3. i=1, j=2: ‘c’ == ‘c’ ✓ (i=2, j=3)
4. i=2, j=3: ‘e’ ≠ ‘d’ ✗ (j=4)
5. i=2, j=4: ‘e’ == ‘e’ ✓ (i=3, j=5) ผลลัพธ์: true (i=3 เท่ากับความยาวของ s)

ตัวอย่างที่ 2

s = "aec"
t = "abcde"

การทำงาน:

1. i=0, j=0: ‘a’ == ‘a’ ✓ (i=1, j=1)
2. i=1, j=1: ‘e’ ≠ ‘b’ ✗ (j=2)
3. i=1, j=2: ‘e’ ≠ ‘c’ ✗ (j=3)
4. i=1, j=3: ‘e’ ≠ ‘d’ ✗ (j=4)
5. i=1, j=4: ‘e’ == ‘e’ ✓ (i=2, j=5) ผลลัพธ์: false (i=2 ไม่เท่ากับความยาวของ s)