I am given a jumbled string : "OTNWEHRE"
Now from this I have to extract the words "ONE" "TWO" "THREE" and print them in the numeric form 1 2 3
So, my approach was to store all the words "ZERO,ONE,TWO,THREE,...." in a character array first and then run a loop through the string input, and compare the string elements with the character array(O' of string i/p with characters of array ['Z','E','R'..]). If the character matches('O' of string input will match at 'O' of ONE) I would then increment through the characters in the char-array(after O matches loop through 'N' then 'E'then ',') and check if these elements are present in the string input. If the characters match till the next ',' I will print the number.
However there is a problem with my algorithm, digits like four and five or six and seven start with the same character but are followed by different characters.
Here's my code anyway
public static void main(String args[])
{ int i,j,a; String wrd=""; checknum o = new checknum(); Scanner sc = new Scanner(System.in); String s =sc.nextLine(); String z= "zero,one,two,three,four,five,six,seven,eight,nine,"; char[] c = z.toCharArray(); for(i=0;i<s.length();i++) { wrd =""; for(j=0;j<c.length;j++) { if(s.charAt(i)==c[j]) { wrd = wrd+c[j]; while(c[j] != ',') { j++; if(s.indexOf(c[j])>=0) wrd = wrd+c[j]; else{ wrd=""; break; } } if(wrd!=null){ a=o.checknumber(wrd); System.out.println(a); } } } }
}PS
if my approach is completely wrong and there's any other way i should go about this problem please let me know.
5 Answers
If I understand correctly, numbers can share characters. (E.g. there is only one T in your example, but both TWO and THREE are included.)
Collect the number of all characters from the String in a HashMap:
String s = ...;
HashMap<Character, Integer> charCount = new HashMap<>();
for (char c : s.toCharArray()) { Integer count = charCount.get(c); if (count == null) count = 0; map.put(c, ++count);
}That way you only have to loop over your String once.
Then you can store each number as its own HashMap with character/integer pairs, e.g. THREE is stored as {{T,1},{H,1},{R,1},{E,2}}.
You can then loop over each number map and check if charCount contains each character (key) from the current number and if the count (value) is greater or equal.
Or create some kind of tree structure for your number characters like so:
_____ | O,1 | |_____| / \ _____/ \_____ | E,1 | | W,1 | |_____| |_____| / \ \ _____/ \_____ \_____
| N,1 | | R,1 | | T,1 |
|_____| |_____| |_____| v | v "ONE" __|__ "TWO" | Z,1 | |_____| v "ZERO"Then walk through it and every leaf you reach is a number contained:
// pseudocode
recursiveCheck(node) { if (charCount.containsKey(node.character) && charCount.get(node.character) > node.count) { if (node.hasChildren()) { for (childnode in node) { recursiveCheck(childnode); } } else { // node is leaf, node.number is contained } }
}One way to solve is -
Pseudo Code
String [ ] str ={"ZERO","ONE"..};
char[ ] input = {'O','T','N','W','H','E','R','E'};
char [ 26 ] temparray;
For i in input temparray[i]++; //Consider 'a'=index 0, 'a' =index 1 ... And so on
For i in str char[ ] temparray2 = str[i].toCharArray(); For j in temparray2 temparray2 [j]++; //Consider 'a'=index 0, 'a' =index 1 ... And so on For j in temparray2 For k in temparray temparray[k]==temparray2 [j]
// If they are equal, print. If not come out of the loopNOTE: I have just gave you hint to write a logic for it. You try to code it. And there are many other ways to optimize it too.
2public class Solution{ public static void main(String args[]){ Scanner sc = new Scanner(System.in); String query = sc.nextLine(); String ans = solve(query); System.out.println(ans); } private String solve(String query){ int fmap[] = new int[27]; for(char x : query.toCharArray()){ fmap[x - 'a']++; } StringBuilder sb = new StringBuilder(""); while(fmap['w' - 'a']-- != 0){ fmap['t'-'a']--; fmap['o'-'a']--; sb.append('2'); } while(fmap['g' - 'a']-- != 0){ fmap['e'-'a']--; fmap['i'-'a']--; fmap['h'-'a']--; fmap['t'-'a']--; sb.append('8'); } while(fmap['z' - 'a']-- != 0){ fmap['e'-'a']--; fmap['r'-'a']--; fmap['o'-'a']--; sb.append('0'); } while(fmap['x' - 'a']-- != 0){ fmap['s'-'a']--; fmap['i'-'a']--; sb.append('6'); } while(fmap['u' - 'a']-- != 0){ fmap['f'-'a']--; fmap['o'-'a']--; fmap['r'-'a']--; sb.append('4'); } while(fmap['u' - 'a']-- != 0){ fmap['f'-'a']--; fmap['o'-'a']--; fmap['r'-'a']--; sb.append('4'); } while(fmap['o' - 'a']-- != 0){ fmap['e'-'a']--; fmap['n'-'a']--; sb.append('1'); } while(fmap['t' - 'a']-- != 0){ fmap['e'-'a']-=2; fmap['h'-'a']--; fmap['r'-'a']--; sb.append('3'); } while(fmap['f' - 'a']-- != 0){ fmap['e'-'a']--; fmap['i'-'a']--; fmap['v'-'a']--; sb.append('5'); } while(fmap['s' - 'a']-- != 0){ fmap['e'-'a']-=2; fmap['n'-'a']--; fmap['v'-'a']--; sb.append('7'); } while(fmap['i' - 'a']-- != 0){ fmap['n'-'a']-=2; fmap['e'-'a']--; sb.append('9'); } }
}
/*
if 'w' -> there is two
if 'g' -> there is eight
if 'z' -> there is zero
if 'x' -> there is six
if 'u' -> there is four
after removing these one, three, five, seven, nine remain (if present)
if 'o' -> there is one. left: {three, five, seven, nine}
if 't' -> there is three. left: {five, seven, nine}
if 'f' -> there is five. left: {seven, nine}
if 's' -> there is seven. left: {nine}
if 'i' -> there is nine. left: {}
*/I did not use any algorithms but rather used uniqueness in each number in word format and it worked like a charm for many test cases I ran against.
The idea was 0 - zero is unique as it has character z and no other number has z in them 2 - has w 4 - has u 6 - has x
Below is the code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.*; public class Yash { /** * Iterate through each line of input. */ public static void main(String[] args) throws IOException { InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8); BufferedReader in = new BufferedReader(reader); String line; String number0 = ""; String number1 = ""; String number2 = ""; String number3 = ""; String number4 = ""; String number5 = ""; String number6 = ""; String number7 = ""; String number8 = ""; String number9 = ""; while ((line = in.readLine()) != null) { Map<Character, Integer> chracterMap = new HashMap<>(); for (int i = 0; i < line.length(); i++) { if (chracterMap.get(line.charAt(i)) == null) { chracterMap.put(line.charAt(i), 1); } else { chracterMap.put(line.charAt(i), chracterMap.get(line.charAt(i)) + 1); } } if (chracterMap.get('z') > 0) { for (int i = 0; i < chracterMap.get('z') ;i++) { number0 = number0 + Integer.toString(0); } chracterMap.put('e', chracterMap.get('e') - chracterMap.get('z')); chracterMap.put('r', chracterMap.get('r') - chracterMap.get('z')); chracterMap.put('o', chracterMap.get('o') - chracterMap.get('z')); } if (chracterMap.get('w') > 0) { for (int i = 0; i < chracterMap.get('w') ;i++) { number2 = number2 + Integer.toString(2); } chracterMap.put('t', chracterMap.get('t') - chracterMap.get('w')); chracterMap.put('o', chracterMap.get('o') - chracterMap.get('w')); } if (chracterMap.get('u') > 0) { for (int i = 0; i < chracterMap.get('u') ;i++) { number4 = number4 + Integer.toString(4); } chracterMap.put('f', chracterMap.get('f') - chracterMap.get('u')); chracterMap.put('o', chracterMap.get('o') - chracterMap.get('u')); chracterMap.put('r', chracterMap.get('r') - chracterMap.get('u')); } if (chracterMap.get('x') > 0) { for (int i = 0; i < chracterMap.get('x') ;i++) { number6 = number6 + Integer.toString(6); } chracterMap.put('s', chracterMap.get('s') - chracterMap.get('x')); chracterMap.put('i', chracterMap.get('i') - chracterMap.get('x')); } if (chracterMap.get('g') > 0) { for (int i = 0; i < chracterMap.get('g') ;i++) { number8 = number8 + Integer.toString(8); } chracterMap.put('e', chracterMap.get('e') - chracterMap.get('g')); chracterMap.put('i', chracterMap.get('i') - chracterMap.get('g')); chracterMap.put('h', chracterMap.get('h') - chracterMap.get('g')); chracterMap.put('t', chracterMap.get('t') - chracterMap.get('g')); } if (chracterMap.get('f') > 0) { for (int i = 0; i < chracterMap.get('f') ;i++) { number5 = number5 + Integer.toString(5); } chracterMap.put('v', chracterMap.get('v') - chracterMap.get('f')); chracterMap.put('i', chracterMap.get('i') - chracterMap.get('f')); chracterMap.put('e', chracterMap.get('e') - chracterMap.get('f')); } if (chracterMap.get('r') > 0) { for (int i = 0; i < chracterMap.get('r') ;i++) { number3 = number3 + Integer.toString(3); } chracterMap.put('t', chracterMap.get('t') - chracterMap.get('r')); chracterMap.put('h', chracterMap.get('h') - chracterMap.get('r')); chracterMap.put('e', chracterMap.get('e') - chracterMap.get('r') - chracterMap.get('r')); } if (chracterMap.get('i') > 0) { for (int i = 0; i < chracterMap.get('i') ;i++) { number9 = number9 + Integer.toString(9); } } if(chracterMap.get('s') > 0) { for (int i = 0; i < chracterMap.get('s') ;i++) { number9 = number9 + Integer.toString(7); } } if(chracterMap.get('o') > 0) { for (int i = 0; i < chracterMap.get('o') ;i++) { number1 = number1 + Integer.toString(1); } } System.out.println(number0 + number1+ number2 + number3 + number4+ number5 + number6 + number7 + number8+ number9); } } }You can solve this in two possible ways:
1. Backtracking (ie Brute Force): Not Optimal
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
public class Problem2 { private final String[] numStrings = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; private List<Integer> result; public static void main(String[] args) { String input = "notonssvifuineexoonnehefoeengneineiefevevsfteuiifvoteuoiitegfsogneniohnfifxrevunrrewwneurenteeisoionvinhnr"; Problem2 problem1 = new Problem2(); System.out.println(problem1.solveBruteForce(input)); } public List<Integer> solveBruteForce(String jumbledNums) { List<Character> currCharList = jumbledNums.chars().mapToObj(c -> (char) c).collect(Collectors.toList()); List<Integer> currPath = new ArrayList<>(); backtrack(currCharList, currPath); // Depends on your requirement Collections.sort(result); return result; } private void backtrack(List<Character> currentCharList, List<Integer> path) { if (currentCharList.size() == 0) { //base condition result = new ArrayList<>(path); return; } for (int i = 0; i <= 9; i++) { // find all the possible next states String numString = numStrings[i]; if (contains(currentCharList, numString)) { // if currNum String is present in the input String // 1. Remove for (char numChar : numString.toCharArray()) currentCharList.remove(Character.valueOf(numChar)); path.add(i); // 2. Backtrack backtrack(currentCharList, path); // 3. Add it back for (char numChar : numString.toCharArray()) currentCharList.add(numChar); path.remove(path.size() - 1); } } } private boolean contains(List<Character> currentCharList, String numString) { for (Character numChar : numString.toCharArray()) { List<Character> stringList = numString.chars().mapToObj(c -> (char) c).collect(Collectors.toList()); int freqOfCharWithinNumString = Collections.frequency(stringList, numChar); int freqOfCharWithinCurrentCharList = Collections.frequency(currentCharList, numChar); if (freqOfCharWithinCurrentCharList < freqOfCharWithinNumString) { return false; } } return true; }
}2. The better optimal solution is to identify the pattern within the numbers.
Step 1: Let's enumerate all the number strings.
+----------------+
| Number Strings |
+----------------+
| zero |
| one |
| two |
| three |
| four |
| five |
| six |
| seven |
| eight |
| nine |
+----------------+Step 2: We see that for even numbers, we have a unique character in each of them.
+----------------------+------------------+
| Even Number Strings | Unique Character |
+----------------------+------------------+
| zero | z |
| two | w |
| four | u |
| six | x |
| eight | g |
+----------------------+------------------+Using the frequency of z, we can find the count of "zero" in the String.
Using these unique characters, we can deterministically find the frequency of the even numbers.
Step 3: Now, for odd numbers, we don't have such unique characters. This is when we use even number's frequency determinism to deduce odd numbers frequency.
+---------------------+-----------------------------+
| Even(Deterministic) | Odd (Not yet Deterministic) |
+---------------------+-----------------------------+
| zero | one |
| two | three |
| four | five |
| six | seven |
| eight | nine |
+---------------------+-----------------------------+Let's take the number "one". The character o is present in "one" from the odd set and "zero", "two" & "four" from the even set.
Let's maintain one's frequency based on the number of o's present in the String.
Note that even set is already deterministic.
So, we can deduce one's frequency deterministically, by removing the duplicate frequency of "zero", "two" & "four".
freq[1] = freq[1] - (freq[0] + freq[2] + freq[4]);We can extend this to the rest of the four numbers in the odd set.
Step 4: Talk is cheap, show me the code.
import java.util.ArrayList;
import java.util.List;
public class Problem2 { private final String[] numStrings = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; public static void main(String[] args) { String input = "notonssvifuineexoonnehefoeengneineiefevevsfteuiifvoteuoiitegfsogneniohnfifxrevunrrewwneurenteeisoionvinhnr"; Problem2 problem1 = new Problem2(); System.out.println(problem1.solveOptimal(input)); } public List<Integer> solveOptimal(String jumbledNums) { int[] freq = new int[10]; for (char numChar : jumbledNums.toCharArray()) { // Even Nums if (numChar == 'z') freq[0]++; if (numChar == 'w') freq[2]++; if (numChar == 'u') freq[4]++; if (numChar == 'x') freq[6]++; if (numChar == 'g') freq[8]++; // Odd Nums if (numChar == 'o') freq[1]++; // o is present in one, {zero, two, four} if (numChar == 'h') { // h is present in three, {eight}. // NOTE: You could also take t, but would need more operations freq[3]++; } if (numChar == 'f') freq[5]++; // f is present in five, {four} if (numChar == 's') freq[7]++; // s is present in seven, {six} if (numChar == 'i') { // i is present in nine, five, {six, eight}. // NOTE: Make sure to make five deterministic before doing this step. Order Matters. freq[9]++; } } freq[1] -= (freq[0] + freq[2] + freq[4]); freq[3] -= freq[8]; freq[5] -= (freq[4]); freq[7] -= freq[6]; freq[9] -= (freq[5] + freq[6] + freq[8]); List<Integer> result = new ArrayList<>(); for (int i = 0; i <= 9; i++) { for (int j = 1; j <= freq[i]; j++) { result.add(i); } } // Quick Validation Logic int ansCount = 0; for (int entry : result) { ansCount += numStrings[entry].length(); } System.out.println("Answer Count " + ansCount + " Question Count " + jumbledNums.length()); System.out.println("Answer is correct " + (ansCount == jumbledNums.length())); return result; }
}Reference: Geek4Geeks
