Bhaskar
BAN USERMy solution to store letters in a HashSet is incorrect because HashSet don't store duplicates. In order to determine if a word can be formed from the given list of acceptable letters create another HashMap<String, Integer> where String represents every letter in the letter set and Integer represents its count.
For every character in the string reduce the count for that particular character in the hashmap by 1. You can also create array[256] instead of hashmap.
For a string s of length n, if the character at n-3 isn't in the hashmap/array then the string cannot be formed. Before the operation repeats with the next string, the hashmap/array should be re-created from the letter set. Instead of traversing the entire letter set start from the position n-3 in string s and work backwards thereby increasing the count of every character encountered.
Group the words according to their lengths in a HashMap<Integer, ArrayList<String>>. Traverse the hashmap starting with the largest key value (indicates group of words of similar length) and determine if there is at least one word which can be formed from the parameters. If there is one or more words print it out and stop execution once the list is completely traversed. If not continue on to the next smallest group of words.
In order to determine if a word can be formed from the given list of acceptable letters, create a hashset of the acceptable letters and use set_object.contains(s.charAt(index)) to do so, where s represents the string from the ArrayList.
One way of doing this is to generate the bits in-place and print the string once all the ‘?’ are replaced appropriately.
public static void printString (StringBuilder s, ArrayList<Integer> spots, int j){
if (j==spots.size()){
System.out.println(s.toString());
return;
}
StringBuilder t = new StringBuilder ();
char c=’0’;
for (int i=0;i<2;i++){
t.append(s.substring(0,spots.get(j)));
t.append(c);
t.append(s.substring(spots.get(j)+1));
printString (t, spots, j+1);
t.delete(0,t.length());
c = ‘1’;
}
}
public static void printString (StringBuilder s){
ArrayList<Integer> spots = new ArrayList<Integer>();
StringBuilder gen = new StringBuilder ();
for (int i=0;i<s.length();i++)
if (s.charAt(i) == ‘?’)
spots.add(i);
printString (s, spots, 0);
}
Naive Recursion
public static int minJums(int [] a , int i){
if (i == a.length-1) return 0;
int min = a.length;
for (int k = i+1; k<=a.length && k < = i + a[i] ; k++)
min = Math.min (min, minJumps (a,k));
return min+1;
}
Dynamic Programming: Time: O(N^2). Space: O(N)
int minJump(int [] a){
int [] = new jump [n];
jump [n-1] = 0;
for (int i=n-2; i>=0; i--){
int min = a.length;
for (int j=i+1; j<n && j<=i +a[i]; j++)
min = Math.min (min, jumps[j]);
jumps[i]=min+1;
}
return jumps[0];
}
Consider singly linked list 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> NULL.
- Bhaskar September 08, 2014The head and n is pointing to 1.
Remember n is a reference to the head of the linked list and not the head itself.
By moving n along the linked list (say you are at 4 now) you are moving the reference along the linked list, the head essentially stays at 1, its just that you have lost the reference to head (1) because you have moved your only reference (n) to 4.
The reason why you are being able to move the reference along the linked list is because every LinkedListNode object n is referencing to has a pointer (reference in OO) to the next object. You continue to move along the linked list until you run out of references which is encounter NULL.
Having another reference (n1) pointing to the head saves the day.