Extract numbers from a jumbled string

Question

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.

Answer 1

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 ch : jumbledNums.toCharArray()) {
            ch = Character.toLowerCase(ch);
            
            //direct answer, unique characters only present in single numeral
            //doing this is important, order matters
            if (ch == 'z') freq[0]++; // only present in ZERO 
            if (ch == 'w') freq[2]++; // only present in TWO 
            if (ch == 'u') freq[4]++; // only present in FOUR 
            if (ch == 'x') freq[6]++; // only present in SIX 
            if (ch == 'g') freq[8]++; // only present in EIGHT 

            //indirect answer, only update for numbers which are not yet determined
            if (ch == 'o') freq[1]++; // present in ONE, (ZERO, TWO, FOUR)
            if (ch == 'h') freq[3]++; // present in EIGHT, (THREE) 
            if (ch == 'f') freq[5]++; // present in FIVE, (FOUR)
            if (ch == 's') freq[7]++; // present in SEVEN, (SIX)
            if (ch == 'i') freq[9]++; // present in NINE, {FIVE, SIX, EIGHT}
        }
        
        // Count is indirect numbers that can be found by subtracting freq of related numbers which are already found
        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

Answer 2

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);   
            }    
        }
    }

Answer 3

public 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: {}




*/

Answer 4

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
        }
    }
}

Answer 5

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 loop

NOTE: 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.