In the code below I have a double for loop resulting in a time complexity of O^2 in method getResponse(). This code prompts the user for a 10 integer sequence string and an uppercase sensitive pin. It then converts the pin to numbers on a phone pad ie. [ABC] --> 2, [DEF] --> 3. Lastly a response array is generated with each digit of the new phone pin corresponding to indexes of sequence. So input "0123456789","HAM", response = "426"

import java.util.Scanner;

public class Test {


    public static final int SEQ_DIGITS = 10;


    public static final String ERR_SEQ = "Invalid sequence";


    public static final String ERR_PIN = "Invalid PIN";

    public static int letterToPhone(char c) {
        int phoneNumber = 0;
        if (Character.toString(c).matches("[ABC]")) {
            phoneNumber = 2;
        } else if (Character.toString(c).matches("[DEF]")) {
            phoneNumber = 3;
        } else if (Character.toString(c).matches("[GHI]")) {
            phoneNumber = 4;
        } else if (Character.toString(c).matches("[JKL]")) {
            phoneNumber = 5;
        } else if (Character.toString(c).matches("[MNO]")) {
            phoneNumber = 6;
        } else if (Character.toString(c).matches("[PQRS]")) {
            phoneNumber = 7;
        } else if (Character.toString(c).matches("[TUV]")) {
            phoneNumber = 8;
        } else if (Character.toString(c).matches("[WXYZ]")) {
            phoneNumber = 9;
        }

        return phoneNumber;
    }


    public static int[] getResponse(String pin, int[] values) {
        int[] response = new int[pin.length()];

        for(int i = 0; i < pin.length(); i  ) {
            for (int j = 0; j < values.length; j  ) {
                int x = letterToPhone(pin.charAt(i));
                if(x == j) {
                    response[i] = values[j];
                }   
            }
        }

        return response;
    }


    public static boolean stringIsLengthK(String s, int k) {
        boolean isLength = false;

        if (s.length() == k) {
            isLength = true;
        }

        return isLength;

    }

    public static boolean allDigits(String s) {
        boolean isDigit = true;
        for (int i = 0; i < s.length(); i  ) {
            if (!(Character.isDigit(s.charAt(i)))) {
                isDigit = false;
                break;
            }
        }
        return isDigit;
    }


    public static boolean allUppercaseLetters(String s) {
        boolean isUpper = true;

        for (int i = 0; i < s.length(); i  ) {
            if (!(Character.isUpperCase(s.charAt(i)))) {
                isUpper = false;
                break;
            }
        }
        return isUpper; 
    }

    public static int[] digitStringToIntArray(String s) {
        int[] arrayS = new int[s.length()];

        for(int i = 0; i < arrayS.length; i  ) {
            for(int j = 0; j < SEQ_DIGITS; j  ) {
                if (((int) s.charAt(i) - 48) == j) {

                    arrayS[i] = j;
                }
            }

        }
        return arrayS; 
    }

    public static int countValues(int value, int[] values) {
        int count = 0;
        for(int i = 0; i < values.length; i  ) {
            if(value == values[i]) {
                count  ;
            }
        }
        return count;
    }
    public static int numPossible(int[] response, int[] values) {
        int product = 1;
        int[] count = new int[response.length];
        
        
        for (int i = 0; i < count.length; i  ) {
            count[i] = countValues(response[i], values);
            
        }
        
        for(int i=0; i<response.length; i  ){
             product = product * count[i];
          }
        return product; 
    }

    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            System.out.printf("Enter value sequence: ");
            final String seq = in.nextLine();

            System.out.printf("Enter PIN: ");
            final String pin = in.nextLine();

            if (!(allUppercaseLetters(pin))) {
                throw new AssertionError(ERR_PIN);
            } else if (!(allDigits(seq)) || !(stringIsLengthK(seq, SEQ_DIGITS))) {
                throw new AssertionError(ERR_SEQ);
            }

            

            int[] seqArray = new int[SEQ_DIGITS];
            seqArray = digitStringToIntArray(seq);

            int[] response = new int[SEQ_DIGITS];
            response = getResponse(pin, seqArray);
            
            System.out.printf("Response: ");
            
            for (int i = 0; i < response.length; i  ) {
                System.out.printf("%d", response[i]);
            }
            
            System.out.printf("%n");
            numPossible(response, seqArray);
            
            
        } catch (Error e) {
            System.out.println(e.getMessage());
        }

        

    }

}

I want to be to able to accommodate larger sequence numbers without a scaling of n^2. Is there a way to change the for loop to instead compare the int x = letterToPhone(pin.charAt(i)); value in getResponse() to a range of integers such as "[0-9]"

CodePudding user response：

One easy optimization of constant factors is to move the call to letterToPhone() out of the inner loop.

And yes, you can compare the x value to a range, eliminating the need for the inner loop.

    for(int i = 0; i < pin.length(); i  ) {
        int x = letterToPhone(pin.charAt(i));

        if ( (0 < x) && (x < values.length)) {
            response[i] = values[x];
        }
    }

Another optimization of constant factors would be to replace all the function calls in letterToPhone() with a switch statement. The compiler may choose to optimize that into a table lookup.