Farooq
BAN USERI work for a well known car company and love coding and practicing these algorithms :)
- » Farooq Blog
- » Linked In
Check linked in:
http://www.linkedin.com/pub/farooq-khera/79/977/703
So the complexity on this problem is pretty huge, right?
potentially you are having to loop through the characters provided in your first string, I guess we can say for each character -> it has n encodings.
My problem appears to represent recurrence relation
T(n-1) + O(n^2) = O(n^3) ... does that seem right?
I may have to look this up.
I agree with the previous comments, this problem is exactly like the phone dialer problem.
public List<String> generatePasswords(String password, Map<Character, List<Character>> encodings)
{
List<String> results = new ArrayList<String>();
if(password.isEmpty())
{
results.add("");
return results;
}
//get the encodings of the first character, iterate for all encodings create passwords
char firstChar = password.charAt(0);
List<Character> firstCharEncodings = encodings.get(firstChar);
//firstCharEncodings.add(firstChar);
List<String> words = generatePasswords(password.substring(1), encodings);
for(String word: words)
{
String result = firstChar + word;
results.add(result);
}
for(Character firstCharEncoding : firstCharEncodings)
{
String result = "";
for(String word: words)
{
result = firstCharEncoding + word;
results.add(result);
}
}
return results;
}
Map<Character, List<Character>> encodings = new HashMap<Character, List<Character>>();
encodings.put('a', Arrays.asList('1','2','p','o','q'));
encodings.put('b', Arrays.asList('2','y'));
encodings.put('c', Arrays.asList('p'));
encodings.put('d', Arrays.asList('4','a','m','n'));
encodings.put('e', Arrays.asList('9','z','x'));
List<String> generatedPasswords = newObj.generatePasswords("abcde", encodings);
System.out.println(Arrays.toString(generatedPasswords.toArray()));
I think of this problem a little bit like the partitioning problem in quick sort.
We can think of there being a wall in the place that is our first zero.
1,0,2,0,0,3,4
In general the steps will be.
Find the first zero, lets call this the wall.
Now iterate all indexes after the current wall position such that the value is a non zero value.
If we find a non zero , then lets swap the current wall value which is a zero with the new value, and lets increment our wall position.
Keep going until the currentIndex < length.
Lets see if I can visualize this:
1,0,2,0,0,3,0,4
So our first zero is the #1 index
1,0|,2,0,0,3,0,4
swap our first non zero value with the wall
1,2|0,0,0,3,0,4
increment the wall
1,2,0|,0,0,3,0,4
Then rinse and repeat
void partitionArray(int [] array)
{
int currentIndex = 0;
int currentWall = 0;
//Find first non zero value
for(int i = 0; i<array.length; i++)
{
if(array[i] == 0)
{
currentWall = i;
break;
}
}
currentIndex = currentWall + 1;
while(currentIndex < array.length)
{
if(array[currentIndex] != 0)
{
//swap this item with the wall
int temp = array[currentIndex];
array[currentIndex] = array[currentWall];
array[currentWall] = temp;
//move the wall
currentWall++;
}
currentIndex++;
}
}
I think of this problem a little bit like the partitioning problem in quick sort.
We can think of there being a wall in the place that is our first zero.
1,0,2,0,0,3,4
In general the steps will be.
Find the first zero, lets call this the wall.
Now iterate all indexes after the current wall position such that the value is a non zero value.
If we find a non zero , then lets swap the current wall value which is a zero with the new value, and lets increment our wall position.
Keep going until the currentIndex < length.
Lets see if I can visualize this:
1,0,2,0,0,3,0,4
So our first zero is the #1 index
1,0|,2,0,0,3,0,4
swap our first non zero value with the wall
1,2|0,0,0,3,0,4
increment the wall
1,2,0|,0,0,3,0,4
Then rinse and repeat
void partitionArray(int [] array)
{
int currentIndex = 0;
int currentWall = 0;
//Find first non zero value
for(int i = 0; i<array.length; i++)
{
if(array[i] == 0)
{
currentWall = i;
break;
}
}
currentIndex = currentWall + 1;
while(currentIndex < array.length)
{
if(array[currentIndex] != 0)
{
//swap this item with the wall
int temp = array[currentIndex];
array[currentIndex] = array[currentWall];
array[currentWall] = temp;
//move the wall
currentWall++;
}
currentIndex++;
}
}
h public void printNonComments(String text)
{
boolean activeComment = false;
System.out.println("input text: " + text);
for(int i=0; i<text.length()-1; i++)
{
String textToCompare = "" + text.charAt(i) + text.charAt(i+1);
//System.out.println("current text to compare: " + textToCompare);
if(textToCompare.equals( "/*"))
{
//System.out.println("FOUND A COMMENT ----------");
activeComment = true;
//i=i+2;
}
else if (textToCompare.equals("*/"))
{
activeComment = false;
i=i+1;
}
else if(activeComment == false || textToCompare.contains("\r"))
{
System.out.print(text.charAt(i));
}
}
if(activeComment == false)
{
System.out.print(text.charAt(text.length()-1));
}
}
Repannaharricks, Computer Scientist at ABC TECH SUPPORT
Hi, I am a Social worker to help people handle everyday life problems. I also assist people who have issues ...
It would appear we can generate O(m^n) . If m is the length of the encodings, and n is the length of the initial password.
- Farooq October 13, 2014