3407. Substring Matching Pattern - Easy

前往題目

想法

• 直接匹配，略過星號

思路

1. 以星號為準切分p
2. 嘗試匹配第一段與第二段p

Code

以下是不用 built-in 方法的寫法

class Solution {
    public boolean hasMatch(String s, String p) {
        // star index
        int index = -1;

        for (int i = 0; i < p.length(); ++i) {
            if (p.charAt(i) == '*') {
                index = i;
                break;
            }
        }

        int num1 = check(s, p.substring(0, index));
        if (num1 == -1) return false;
        int num2 = check(s.substring(num1), p.substring(index + 1));
        return num2 != -1;
    }

    private int check(String s, String p) {
        int n = s.length();
        int m = p.length();

        int j = 0;
        // Iterate through string s, pattern matching
        // <= n - m in case out of bound
        for (int i = 0; i <= n - m; ++i) {
            // string p
            for (j = 0; j < m; ++j) {
                char c1 = s.charAt(j + i);
                char c2 = p.charAt(j);

                if (c1 != c2) break;
            }
            // Pattern matched, return tail index + 1
            if (j == m) return i + j;
        }

        return -1; // Matching failed
    }
}