Alg.19 Pattern Matcher

From algoexpert.io

We’re given 2 non-empty strings. The first one is a pattern consisting of only “x” and “y”, the other one is a normal string of alphanumeric characters. Write a function that checks whether the normal string matches the pattern. Here is a sample:



First, we need a function to transform the pattern like “yyxx” into “xxyy”.

/**
     * To make the process more straightforward, we transform all 
     * the patterns like "yyxx" into "xxyy"
     */
    public static String transform(String pattern) {
        if (pattern.charAt(0) == 'x') {
            return pattern;
        } else {
            StringBuilder trans = new StringBuilder();
            for (int i = 0; i < pattern.length(); i++) {
                if (pattern.charAt(i) == 'x') {
                    trans.append('y');
                } else {
                    trans.append('x');
                }
            }
            return trans.toString();
        }
    }

Then, we need a function to get first y’s position and the number of x and y.

/**
     * Get first y's position and count the number of "x" and "y"
     */
    public static int getYPos(Map<Character, Integer> map, String pattern) {
        int yPos = -1;
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (pattern.charAt(i) == 'y' && yPos == -1) {
                yPos = i;
            }
            map.put(c, map.get(c) + 1);
        }
        return yPos;
    }

Here is the function that we can generate the potential match string according to the pattern, x and y.

/**
     * Get the potential match string according to "pattern", "x" and "y"
     */
    public static String buildPotentialString(String pattern, String x, String y) {
        StringBuilder potential = new StringBuilder();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (c == 'x') {
                potential.append(x);
            } else {
                potential.append(y);
            }
        }
        return potential.toString();
    }

We can solve the problem now, here is the main function.

public static String[] patternMatcher(String pattern, String str) {
        String trans = transform(pattern); // Transform the given pattern
        boolean wasChanged = trans.charAt(0) != pattern.charAt(0);
        Map<Character, Integer> map = new HashMap<>();
        map.put('x', 0);
        map.put('y', 0);
        int yPos = getYPos(map, trans); // Get first y's position and number of x and y
        int xNum = map.get('x');
        int yNum = map.get('y');
        if (yPos != -1) {
            for (int xLen = 1; xLen < str.length(); xLen++) {
                // Use double to store y's length so that we can determine whether it's valid
                double yLen = ((double)str.length() - (double)xLen * (double)xNum) / (double)yNum;
                if (yLen <= 0 || yLen % 1 != 0) {
                    continue;
                }
                int yIdx = yPos * xLen;
                String x = str.substring(0, xLen);
                String y = str.substring(yIdx, yIdx + (int)yLen);
                String potentialMatch = buildPotentialString(trans, x, y);
                if (str.equals(potentialMatch)) {
                    return wasChanged ? new String[] {y, x} : new String[] {x, y};
                }
            }
        } else {
            double xLen = str.length() / xNum;
            if (xLen % 1 == 0) {
                String x = str.substring(0, (int)xLen);
                String potentialMatch = buildPotentialString(trans, x, "");
                if (str.equals(potentialMatch)) {
                    return wasChanged ? new String[] {"", x} : new String[] {x, ""};
                }
            }
        }
        return new String[] {};
    }

Time complexity: O(n^2 + m); Space complexity: O(n + m).

Donate