It is Sunday morning in the Twin Cities of Minneapolis and St. Paul. Woke up around 04:30 AM and spent the next couple hours working on Machine Learning with Big Data. It is a Coursera course. Have one more week to complete this course; so far so good. After preparing and having breakfast with my best half, return to my computer.
We will attempt to figure out if two strings can be converted from one to the other following two different sets of rules. The second one I accidentally ran doing a Google search on string conversions. Seems like the challenge was posted in HackerRank and the author wanted to validate the approach. I looked at the proposed solution and decided to use two different approaches. Both seems to work and are less complex than the proposed solution.
Let’s cover the first challenge. Based on experience, it is important to understand and clarify as much as possible what the requirements are before writing any code. The requirements follow:
Given a pair of strings, determine if the first one can be transformed to the second.
The rule is that any character in the first string may be replaced with any other character once.
For example, given string a = “abcd” and string b = “pqrs” we could apply the following set of transformation to the first string, a -> p, b -> q, c -> r, and d -> s, so the first string could be transformed into string b.
Now let’s consider the following pair of strings, a = “abca” and b = “fced”. In this case we could map a -> f, b -> c, c -> e, but the second character a in the first string could not map to character ‘d’ because character ‘a’ has already been mapped to ‘f’, so the first string could not be transformed into the second.
Let’s take a look at the output of the Eclipse IDE:
aa ==>abcd<== bb ==>pqrs<== CanTransform: YES aa ==>abca<== bb ==>dced<== CanTransform: YES aa ==>abca<== bb ==>dxyd<== CanTransform: YES aa ==>PDQ<== bb ==>ACE<== CanTransform: YES aa ==>abc<== bb ==>xy<== CanTransform: NO aa ==>abca<== bb ==>fced<== CanTransform: NO aa ==>abca<== bb ==>fcea<== CanTransform: NO aa ==>abca<== bb ==>dcea<== CanTransform: NO aa ==>abca<== bb ==>aced<== CanTransform: NO
The Java code for the CanTransform() function follows:
/*
* Given a pair of strings, determine if the first can be transformed to the second.
* The only rule is that any character in the first string may be replaced with any
* other character but the new character will remain the same for further replacements
* in order to match the second string.
*
* e.g., a = "abcd"
* b = "pqrs"
* a -> p, b -> q, c -> r, and d -> s could be transformed
*
* e.g., a = "abca"
* b = "fced"
* a -> f, b -> c, c -> e, but a cannot map to d because a has already mapped to f.
*/
static boolean CanTransform(String strA, String strB) {
HashMap<Character, Character> hm = new HashMap<Character, Character>();
char cA;
char cB;
// **** check if lengths do NOT match ****
if (strA.length() != strB.length())
return false;
// **** traverse the input string checking the output string ****
for (int i = 0; i < strA.length(); i++) {
// **** current character from first string ****
cA = strA.charAt(i);
// **** check if already mapped ****
if (hm.containsKey(cA)) {
// **** check if mapping is incorrect ****
if (hm.get(cA) != strB.charAt(i))
return false;
}
// **** NOT mapped ****
else {
cB = strB.charAt(i);
hm.put(cA, cB);
}
}
// **** can transform ****
return true;
}
Please note that the actual transformation was not required. I believe it would be easy to return the second string or for the caller to display it since it was passed to the function as an argument.
The second challenge was originated when I was running a Google search and hit among others the following: Transform String a into b. What called my attention was the amount of complex code that was associated with the request for help. In addition a mention to HackerRank appeared in one of the comments. I tried to locate the challenge in HackerRank but after a minute or so I gave up on it. It seems that the name of the article in StackExchange does not match the title in HackerRank; such is life.
After reading the description a few times, I thought of a simple approach that would use a couple stacks. Following is such implementation:
/*
* You can perform the following operation on some string a:
*
* 1. Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase).
* 2. Delete all of the remaining lowercase letters in a.
*
* Given string a, print YES if it can be transformed to string b.
*
* String a has only capital and small letter alphabets.
* String b has only capital letters.
*/
static boolean Transform(String a, String b) {
Stack<Character> sa = new Stack<Character>();
Stack<Character> sb = new Stack<Character>();
// **** push string a into stack sa ****
for (int i = 0; i < a.length(); i++)
sa.push(a.charAt(i));
// **** push string b into stack sb ****
for (int i = 0; i < b.length(); i++)
sb.push(b.charAt(i));
// **** ****
while (!sa.empty() && !sb.isEmpty()) {
Character ca = sa.peek();
Character cb = sb.peek();
if (ca.equals(cb) || ca.equals(Character.toUpperCase(cb))) {
sb.pop();
sa.pop();
} else if (Character.isLowerCase(ca.charValue())) {
sa.pop();
} else {
return false;
}
}
// **** ****
if (sa.size() != sb.size())
return false;
else
return true;
}
The approach is quite simple. The drawback is that it uses two stacks and the function needs to traverse both strings plus both stacks once. I believe the code is O(4n) or O(2n). After testing that the results matched the ones in the article I decided to eliminate the stacks and use the strings directly.
The code for such approach follows:
/*
* Simpler Transform() without the use of stacks.
* Please see Transform() for requirements.
*/
static boolean TransformNoStack(String a, String b) {
int ia = a.length() - 1;
int ib = b.length() - 1;
// **** ****
while ((ia >= 0) && (ib >= 0)) {
Character ca = a.charAt(ia);
Character cb = b.charAt(ib);
if (ca.equals(cb) || ca.equals(Character.toUpperCase(cb))) {
ia--;
ib--;
} else if (Character.isLowerCase(ca.charValue())) {
ia--;
} else {
return false;
}
}
// **** ****
if (ia != ib)
return false;
else
return true;
}
The code is quite similar to the version using stacks. The results match. Note that this is a O(n) and no additional space is required.
Just to make it simple the complete output captured from the console of the Eclipse IDE follows:
aa ==>abcd<== bb ==>pqrs<== CanTransform: YES aa ==>abca<== bb ==>dced<== CanTransform: YES aa ==>abca<== bb ==>dxyd<== CanTransform: YES aa ==>PDQ<== bb ==>ACE<== CanTransform: YES aa ==>abc<== bb ==>xy<== CanTransform: NO aa ==>abca<== bb ==>fced<== CanTransform: NO aa ==>abca<== bb ==>fcea<== CanTransform: NO aa ==>abca<== bb ==>dcea<== CanTransform: NO aa ==>abca<== bb ==>aced<== CanTransform: NO ---- ---- ---- aa ==>Pi<== bb ==>P<== Transform: YES aa ==>AfPZN<== bb ==>APZNC<== Transform: NO aa ==>LDJAN<== bb ==>LJJM<== Transform: NO aa ==>UMKFW<== bb ==>UMKFW<== Transform: YES aa ==>KXzQ<== bb ==>K<== Transform: NO aa ==>LIT<== bb ==>LIT<== Transform: YES aa ==>QYCH<== bb ==>QYCH<== Transform: YES aa ==>DFIQG<== bb ==>DFIQG<== Transform: YES aa ==>sYOCa<== bb ==>YOCN<== Transform: NO aa ==>JHMWY<== bb ==>HUVPW<== Transform: NO aa ==>BBbcA<== bb ==>BCA<== Transform: NO aa ==>BBb<== bb ==>B<== Transform: NO ---- ---- ---- aa ==>Pi<== bb ==>P<== TransformNoStack: YES aa ==>AfPZN<== bb ==>APZNC<== TransformNoStack: NO aa ==>LDJAN<== bb ==>LJJM<== TransformNoStack: NO aa ==>UMKFW<== bb ==>UMKFW<== TransformNoStack: YES aa ==>KXzQ<== bb ==>K<== TransformNoStack: NO aa ==>LIT<== bb ==>LIT<== TransformNoStack: YES aa ==>QYCH<== bb ==>QYCH<== TransformNoStack: YES aa ==>DFIQG<== bb ==>DFIQG<== TransformNoStack: YES aa ==>sYOCa<== bb ==>YOCN<== TransformNoStack: NO aa ==>JHMWY<== bb ==>HUVPW<== TransformNoStack: NO aa ==>BBbcA<== bb ==>BCA<== TransformNoStack: NO aa ==>BBb<== bb ==>B<== TransformNoStack: NO
The complete Java code including the test program follows:
package canessa.transform.string;
import java.util.HashMap;
import java.util.Stack;
/*
*
*/
public class Solution {
/*
* Given a pair of strings, determine if the first can be transformed to the second.
* The only rule is that any character in the first string may be replaced with any
* other character but the new character will remain the same for further replacements
* in order to match the second string.
*
* e.g., a = "abcd"
* b = "pqrs"
* a -> p, b -> q, c -> r, and d -> s could be transformed
*
* e.g., a = "abca"
* b = "fced"
* a -> f, b -> c, c -> e, but a cannot map to d because a has already mapped to f.
*/
static boolean CanTransform(String strA, String strB) {
HashMap<Character, Character> hm = new HashMap<Character, Character>();
char cA;
char cB;
// **** check if lengths do NOT match ****
if (strA.length() != strB.length())
return false;
// **** traverse the input string checking the output string ****
for (int i = 0; i < strA.length(); i++) {
// **** current character from first string ****
cA = strA.charAt(i);
// **** check if already mapped ****
if (hm.containsKey(cA)) {
// **** check if mapping is incorrect ****
if (hm.get(cA) != strB.charAt(i))
return false;
}
// **** NOT mapped ****
else {
cB = strB.charAt(i);
hm.put(cA, cB);
}
}
// **** can transform ****
return true;
}
/*
* You can perform the following operation on some string a:
*
* 1. Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase).
* 2. Delete all of the remaining lowercase letters in a.
*
* Given string a, print YES if it can be transformed to string b.
*
* String a has only capital and small letter alphabets.
* String b has only capital letters.
*/
static boolean Transform(String a, String b) {
Stack<Character> sa = new Stack<Character>();
Stack<Character> sb = new Stack<Character>();
// **** push string a into stack sa ****
for (int i = 0; i < a.length(); i++)
sa.push(a.charAt(i));
// **** push string b into stack sb ****
for (int i = 0; i < b.length(); i++) sb.push(b.charAt(i)); // **** **** while (!sa.empty() && !sb.isEmpty()) { Character ca = sa.peek(); Character cb = sb.peek(); if (ca.equals(cb) || ca.equals(Character.toUpperCase(cb))) { sb.pop(); sa.pop(); } else if (Character.isLowerCase(ca.charValue())) { sa.pop(); } else { return false; } } // **** **** if (sa.size() != sb.size()) return false; else return true; } /* * Simpler Transform() without the use of stacks. * Please see Transform() for requirements. */ static boolean TransformNoStack(String a, String b) { int ia = a.length() - 1; int ib = b.length() - 1; // **** **** while ((ia >= 0) && (ib >= 0)) {
Character ca = a.charAt(ia);
Character cb = b.charAt(ib);
if (ca.equals(cb) || ca.equals(Character.toUpperCase(cb))) {
ia--;
ib--;
} else if (Character.isLowerCase(ca.charValue())) {
ia--;
} else {
return false;
}
}
// **** ****
if (ia != ib)
return false;
else
return true;
}
/*
*
*/
public static void main(String[] args) {
// **** ****
final int N = 9;
String str = "abcd\r\n" +
"pqrs\r\n" +
"abca\r\n" +
"dced\r\n" +
"abca\r\n" +
"dxyd\r\n" +
"PDQ\r\n" +
"ACE\r\n" +
"abc\r\n" +
"xy\r\n" +
"abca\r\n" +
"fced\r\n" +
"abca\r\n" +
"fcea\r\n" +
"abca\r\n" +
"dcea\r\n" +
"abca\r\n" +
"aced\r\n";
// **** split str ****
String[] splitStr = str.split("\r\n");
// **** process each pair of strings ****
for (int i = 0; i < N; i++) { String aa = splitStr[i * 2]; String bb = splitStr[i * 2 + 1]; System.out.println("aa ==>" + aa + "<=="); System.out.println("bb ==>" + bb + "<==");
System.out.println("CanTransform: " + (CanTransform(aa, bb) ? "YES" : "NO") + "\n");
}
System.out.println("---- ---- ----");
// **** ****
final int Q = 12;
String s = "Pi\r\n" +
"P\r\n" +
"AfPZN\r\n" +
"APZNC\r\n" +
"LDJAN\r\n" +
"LJJM\r\n" +
"UMKFW\r\n" +
"UMKFW\r\n" +
"KXzQ\r\n" +
"K\r\n" +
"LIT\r\n" +
"LIT\r\n" +
"QYCH\r\n" +
"QYCH\r\n" +
"DFIQG\r\n" +
"DFIQG\r\n" +
"sYOCa\r\n" +
"YOCN\r\n" +
"JHMWY\r\n" +
"HUVPW\r\n" +
"BBbcA\r\n" +
"BCA\r\n" +
"BBb\r\n" +
"B\r\n";
// **** split string s ****
String[] ss = s.split("\r\n");
// **** process each pair of strings ****
for (int i = 0; i < Q; i++) { String aa = ss[i * 2]; String bb = ss[i * 2 + 1]; System.out.println("aa ==>" + aa + "<=="); System.out.println("bb ==>" + bb + "<==");
System.out.println("Transform: " + (Transform(aa, bb) ? "YES" : "NO") + "\n");
}
System.out.println("---- ---- ----");
// **** process each pair of strings ****
for (int i = 0; i < Q; i++) { String aa = ss[i * 2]; String bb = ss[i * 2 + 1]; System.out.println("aa ==>" + aa + "<=="); System.out.println("bb ==>" + bb + "<==");
System.out.println("TransformNoStack: " + (TransformNoStack(aa, bb) ? "YES" : "NO") + "\n");
}
}
}
Perhaps I should start posting the code in GitHub to make it easier for readers who want to experiment with the code.
Given that most challenges are quite unique and in general are completely out of what a developer is confronting day to day at work, it is strongly recommended to always read the description a few times, if possible get clarification, and then start coding.
As usual, if you have comments or questions regarding this or any other post in this blog, please drop me a note; will respond as soon as possible.
Keep on learning and experimenting.
John
Follow me on Twitter: @john_canessa