TCHS-6-600

Problem Statement

You have just hacked into your friend's computer, and you want to delete one of his personal files. But wait, why not let him delete it! As you keep watching him, he has a delete command typed in on the terminal which contains a pattern. You want to rename the file to match this pattern so that it gets deleted once he issues the command. You must accomplish this by renaming the given file to a similar name. Other than lowercase letters, a pattern might contain '?' which represents exactly one character (so "a?b" matches "aab", "abb", "acb" etc).

A move is defined as adding a character, deleting a character, or modifying a character from the filename. Given two Strings, file and pattern, return the minimal number of moves required to make the file match the pattern.

Definition

Class:	WildCardMatch
Method:	minimalChanges
Parameters:	String, String
Returns:	int
Method signature:	int minimalChanges(String file, String pattern)
(be sure your method is public)

Constraints

-

file contains between 1 and 50 characters, inclusive.

-

pattern contains between 1 and 50 characters, inclusive.

-

Each character in file will be a lowercase letter ('a'-'z').

-

Each character in pattern will be a lowercase letter ('a'-'z') or '?'

Examples

0)

"abcd"

"bcd"

Returns: 1

Just remove the first character.

1)

"abcd"

"b??"

Returns: 1

Again the first character must be removed.

2)

"aaaabbb"

"aa????b"

Returns: 0

The file already matches the wildcard.

3)

"asdjkhajksdhajksdh"

"asdjkhasdjk?"

Returns: 6

4)

"niceone"

"ieo?e"

Returns: 2

5)

"abcaa"

"abcba"

Returns: 1

Modify just one character.

public class WildCardMatch {

	public static int minimalChanges(String f, String p) {
		int m = f.length(), n = p.length();
		int[][] dp = new int[2][m+1];
		for (int i = 0; i <= m; i++)
			dp[0][i] = i;
		for (int i = 0; i < n; i++) {
			dp[1][0] = i + 1;
			for (int j = 1; j <= m; j++) {
				dp[1][j] = Math.min(dp[0][j], dp[1][j-1]) + 1;
				int c = (p.charAt(i) == f.charAt(j-1)
						|| p.charAt(i) == '?') ? 0 : 1;
				dp[1][j] = Math.min(dp[1][j], dp[0][j-1] + c);
			}
			for (int j = 0; j <= m; j++)
				dp[0][j] = dp[1][j];
		}
		return dp[1][m];
	}

}