ค้นหาสตริงใน Matrix ด้วย Split Function ใน Java

โจทย์: หาสตริงใน Matrix (2D array ของ characters) แนวนอนและแนวตั้ง

ตัวอย่างโค้ด (ปรับปรุง)

import java.util.*;

public class Demo {
    // ค้นหาแนวนอนในแต่ละแถว
    static boolean searchHorizontal(String[] matrix, String target) {
        for (String row : matrix) {
            // ใช้ split - ถ้าพบ target จะได้ array length >= 2
            // หรือ length == 1 แต่ความยาวต่างจากต้นฉบับ (อยู่ขอบ)
            String[] parts = row.split(Pattern.quote(target));
            if (parts.length >= 2 || (parts.length == 1 && !parts[0].equals(row))) {
                return true;
            }
        }
        return false;
    }
    
    // ค้นหาแนวตั้ง: transpose matrix ก่อน
    static String[] transpose(String[] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length();
        String[] transposed = new String[cols];
        
        for (int c = 0; c < cols; c++) {
            StringBuilder sb = new StringBuilder();
            for (int r = 0; r < rows; r++) {
                sb.append(matrix[r].charAt(c));
            }
            transposed[c] = sb.toString();
        }
        return transposed;
    }
    
    public static void main(String[] args) {
        String[] matrix = {"THIS", "SAMPLE", "THIS"};
        String target = "THIS";
        
        boolean found = searchHorizontal(matrix, target) 
                     || searchHorizontal(transpose(matrix), target);
        
        System.out.println(found ? "Found in matrix" : "Not found");
    }
}

ผลลัพธ์

Found in matrix

วิธีอื่น: 2D char Array (直覺กว่า)

static boolean search2D(char[][] grid, String target) {
    int rows = grid.length, cols = grid[0].length;
    int len = target.length();
    
    // Horizontal
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c <= cols - len; c++) {
            boolean match = true;
            for (int k = 0; k < len; k++) {
                if (grid[r][c + k] != target.charAt(k)) { match = false; break; }
            }
            if (match) return true;
        }
    }
    
    // Vertical
    for (int c = 0; c < cols; c++) {
        for (int r = 0; r <= rows - len; r++) {
            boolean match = true;
            for (int k = 0; k < len; k++) {
                if (grid[r + k][c] != target.charAt(k)) { match = false; break; }
            }
            if (match) return true;
        }
    }
    return false;
}

Complexity

• Split method: O(rows × cols × target.length) - split ทำงาน O(n)
• 2D array: O(rows × cols × target.length) - ตรงไปตรงมา เร็วกว่า
• Space: Split method ใช้ O(cols) extra สำหรับ transpose