Almost every different government in the world has a different method of assigning license plates to vehicles. In any of these systems, it is possible to take all possible plates, arrange them in lexicographical order, and number them, where the first plate is 0, the second plate is 1, etc. Your local government has decided to do this with the license plates that it issues, and right before you leave to eat lunch, you have been assigned this daunting project. So that you can actually have a warm meal today, you have decided to write a program to do this for you.
You will be given a String format, containing the format of the local license plates. Each character of format will be either an uppercase letter ('A'-'Z'), a number ('0'-'9'), a space (' '), a dash ('-'), or the lowercase letters 'u', 'n', or 'a'. If the character is a 'u', it means that any uppercase letter can be used in that place. If the character is an 'n', it means that any number can be used in that place. If the character is an 'a', it means that any uppercase letter or number can be used in that place. If the character is not a lowercase letter, then the character in that spot must be the one used in format. For instance, if the format was "AB-una", then "AB-C52" and "AB-D3G" would be legal license plates, but "AC-D3G", "AB-111", and "AB-DEF" would not.
Given the format, you are to return the n-th earliest (0-indexed) license plate that can be formed in this system. If the n-th license plate cannot be formed using the given format, return an empty String. Note that numbers occur earlier lexicographically than letters (e.g., '4' comes before 'B').
|