I had to add this post today. Earlier I was chatting with a software engineer and we were discussing a simple problem. As the discussion progressed a new requirement appeared. After our conversation I decided to just generate this post with two simple solutions. I understand they can be streamed further.
Given some words and some lowercase letters return a list with the words that can be generated with the provided set of lowercase characters. For starters: * A letter may be used multiple times. Second pass: * A letter may NOT be used multiple times.
We are given some words and some letters. Our mission if we wish to accept is to return a list of valid words. A valid word is one that can be generated with the provided letters.
static public List<String> validWords(String[] words, char[] letters) {
}
The signature for the function of interest indicates that we will receive an array of words and an array of characters. The characters are in lowercase. The function returns a list of all the words that are considered valid. That is; they can be generated using the provided list of letters. In the first pass we can use each letter as many times as needed. In the second implementation each letter may only be used once.
We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows computer.
c t a d g f cat dog fat main <<< letters: main <<< words: [cat, dog, fat] validWords <<< map: [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] validWords <<< word ==>cat<== validWords <<< word ==>dog<== validWords <<< word ==>fat<== main <<< validList: [cat, fat] validWords <<< baseMap: [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] validWords <<< word ==>cat<== validWords <<< word ==>dog<== validWords <<< word ==>fat<== main <<< validList: [cat, fat] q n e t n u l list queue tunnel main <<< letters: [q, n, e, t, n, u, l] main <<< words: [list, queue, tunnel] validWords <<< map: [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0] validWords <<< word ==>list<== validWords <<< word ==>queue<== validWords <<< word ==>tunnel<== main <<< validList: [queue, tunnel] validWords <<< baseMap: [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0] validWords <<< word ==>list<== validWords <<< word ==>queue<== validWords <<< word ==>tunnel<== main <<< validList: [tunnel] s i p m i s i a s i p s mississippi miss mia mite main <<< letters: [s, i, p, m, i, s, i, a, s, i, p, s] main <<< words: [mississippi, miss, mia, mite] validWords <<< map: [1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 1, 0, 0, 2, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0] validWords <<< word ==>mississippi<== validWords <<< word ==>miss<== validWords <<< word ==>mia<== validWords <<< word ==>mite<== main <<< validList: [mississippi, miss, mia] validWords <<< baseMap: [1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 1, 0, 0, 2, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0] validWords <<< word ==>mississippi<== validWords <<< word ==>miss<== validWords <<< word ==>mia<== validWords <<< word ==>mite<== main <<< validList: [mississippi, miss, mia]
The first input line holds the letters we are provided. They all are in lowercase.
The second input line contains the words we need to validate.
Our test code displays the arrays in order to verify that all is well before calling the function of interest.
We have the two implementations running one after the other.
In the first test case the first and second implementations return the same words. The word `dog` is not valid because we do not have the letters to generate it.
You can check the other two test cases. The valid words in the first call use the letters multiple times. In the second implementation letters cannot be reused.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** populate array of letters ****
String str = br.readLine().trim().replace(" ", "");
char[] letters = str.toCharArray();
// **** populate array of words ****
String[] words = Arrays.stream(br.readLine().trim().split(" "))
.toArray(String[]::new);
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< letters: " + Arrays.toString(letters));
System.out.println("main <<< words: " + Arrays.toString(words));
// **** invoke function of interest and display valid list of words ****
System.out.println("main <<< validList: " + validWords0(words, letters).toString());
// **** invoke function of interest and display valid list of words ****
System.out.println("main <<< validList: " + validWords1(words, letters).toString());
}
Our test code reads the letters words arrays. The arrays are displayed. The two implementations of the function of interest are called. The associated results are displayed.
/**
* Return a list with the words that can be generated with the
* provided set of lowercase characters.
* A letter may be used multiple times.
*/
static public List<String> validWords0(String[] words, char[] letters) {
// **** initialization ****
List<String> validList = new ArrayList<>();
boolean addToList = true;
// **** sanity check(s) ****
if (words.length == 0) return validList;
if (letters.length == 0) return validList;
// **** populate array with character count - Space: O(26) ****
int[] map = new int[26];
for (char c : letters)
map[Character.valueOf(c) - 'a']++;
// ???? ????
System.out.println("validWords <<< map: " + Arrays.toString(map));
// **** loop once per word - Execution: O(n) ****
for (String word : words) {
// ???? ????
System.out.println("validWords <<< word ==>" + word + "<==");
// **** loop once per character in word - Execution: O(m) ****
addToList = true;
for (char c : word.toCharArray()) {
if (map == 0) {
addToList = false;
break;
}
}
// **** add this word to the validList list (if needed) ****
if (addToList)
validList.add(word);
}
// **** return list of valid words ****
return validList;
}
We perform some initialization followed by some sanity checks.
We will use an array as a hash map. An array is faster and uses less memory. We populate the map with the count of the letters we were given.
We then loop once per word. For each word we check if the characters are in the letters array. If not; we flag as invalid and exit the inner loop. The word is not inserted into the valid list of words if it is not valid. Otherwise; it is inserted in the list.
When all is said and done the list of valid words is returned.
/**
* Return a list with the words that can be generated with the
* provided set of lowercase characters.
* A letter may NOT be used multiple times.
*/
static public List<String> validWords1(String[] words, char[] letters) {
// **** initialization ****
List<String> validList = new ArrayList<>();
boolean addToList = true;
int[] map = null;
// **** sanity check(s) ****
if (words.length == 0) return validList;
if (letters.length == 0) return validList;
// **** populate array with character count - Space: O(26) ****
int[] baseMap = new int[26];
for (char c : letters)
baseMap[Character.valueOf(c) - 'a']++;
// ???? ????
System.out.println("validWords <<< baseMap: " + Arrays.toString(baseMap));
// **** loop once per word - Execution: O(n) ****
for (String word : words) {
// ???? ????
System.out.println("validWords <<< word ==>" + word + "<==");
// **** make a fresh copy of the base map - Space: O(26) ****
map = Arrays.copyOf(baseMap, baseMap.length);
// **** loop once per character in word - Execution: O(m) ****
addToList = true;
for (char c : word.toCharArray()) {
if (map == 0) {
addToList = false;
break;
} else {
map--;
}
// ???? ????
// System.out.println("validWords <<< map: " + Arrays.toString(map));
}
// **** add this word to the validList list (if needed) ****
if (addToList)
validList.add(word);
}
// **** return list of valid words ****
return validList;
}
This implementation is similar to the previous one. As a matter of fact I copied and pasted the code for the previous implementation.
Note that in this case we declare a `baseMap` to keep track of the count of letters we have received. On each loop for a word, we make use of a copy and decrement the counts each time a character is encountered.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John