Print all possible combinations of strings that can be made using a keypad given a number

Consider a phone keypad where every number has few english alphabet characters associated with it. When a user types some numbers on screen , print all possible permutations of string possible using the characters associated with those numbers. Example: if 1 corresponds to A B C and 2 corresponds to DEF. Then number "12" might represent any of the following : AD, AE, AF, BD, BE, BF, CD, CE, CF.
The problem is very similar to this problem.
The key steps in writing an this function are:

• Initialize a keypad array of strings with alphabets corresponding to each number.
• Now one by one choose each of the characters corresponding to the number and recurse.
• Make sure to keep a check for the digit 9 as it will have only 2 characters.

string keypad[9] = {"ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZ"};

void keys(char* num, char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    
    s[start] = keypad[(num[start] - '0' - 1)][0];
    keys(num, s,start+1,end);
    s[start] = keypad[(num[start] - '0' - 1)][1];
    keys(num, s,start+1,end);
    if((num[start] - '0' - 1) < 8)
    {
        s[start] = keypad[(num[start] - '0' - 1)][2];
        keys(num, s,start+1,end);
    }
}

Function to print all permutations of a string!!

Write a function to print all permutations of a string. Characters in the string do not repeat themselves.
The problem is pretty similar to this problem.
Solution is a simple recursive approach where we call the function again and again once with each arrangement of characters. These arrangements are achieved by swapping start with every other character and calling the function again and again with different values of start.

void perm(string s, int start, int end)
{
    //If we have already reached the end of string, print it
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    char temp;
    for(int i=start;i<end;i++)
    {
        SWAP(s[start],s[i],temp);
        perm(s,start+1,end);
        SWAP(s[i],s[start],temp);
    }
}

Print given string in all combinations of uppercase and lowercase characters.

Given a string we need to print the string with all possible combinations of the uppercase and lowercase characters in the string.
So given a string "abc", we need to print the following:
ABC
ABc
AbC
Abc
aBC
aBc
abC
abc
Solution is a simple recursive approach where we call the function again and again once with a character in lower case and another time with the same character in upper case. The code is similar to what we would write for all permutations of a string.

void lowerUpper(char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    //Change next character to upper case
    s[start] = toupper(s[start]);
    lowerUpper(s,start+1,end);

    //Change the same character as changed earlier to lower case
    s[start] = tolower(s[start]);
    lowerUpper(s,start+1,end);
}

Check if string is valid IPv4 ip address

Given a string, we need to print whether the string is a valid IPv4 ip address or not. For example, 12.2.3.4 is valid IP address and 1222.2.22.33 is not.
The key steps in writing an verifyIP function are:

• Length of the string should be less than equal to 15. As each sub part of the IP can be at max 3 digits and we can have at max 3 dots.
• The string should have 4 parts separated by 3 dots.
• Each part should be greater than 0 and less than 256.

void verifyIP(char *s )
{
    int count=0;
    char *str = new char[strlen(s)];
    strcpy(str,s);

    //Check if length of string is greater than 15.
    if(strlen(str)>15)
    {
        cout<<"Not an IP Address"<<endl;
        return;
    }
    
    char *ip=strtok(str,".");
    
    while(ip!=NULL)
    {
        count++;

        //Check that each subpart is less than 256
        if(atoi(ip)>255)
        {
            cout<<"Not an IP address"<<endl;
            return;
        }
        ip=strtok(NULL,".");
    }

    //Check that we have 4 parts in the ip
    if(count==4)
        cout<<"Correct IP Address"<<endl;
    else
        cout<<"Not an IP Address"<<endl;
}

Commafy()

Given a number, convert it to a string and put commas in it after every 3 digits. So given a number say 100054, function should return 100,054 or for a number like 3040005, function should return 3,040,005.
The key steps in writing an commafy function are:

• Check if number is 0. In this case return string "0".
• Check if number is less than zero. Save this information in a variable and make the number positive.
• Extract each digit from the number and add a comma after every 3 digits.
• Make sure to append '-' sign before returning result if the number was negative.
• Remember to reverse the string before returning as we extracted digits LSB first and hence generated string is reverse of expected

const char* commafy(int num)
{
    char *text = new char(10);

    //Check for num == 0
    if(num==0)
        return "0\0";

    int i=0, sign = 1, count = 0;
    
    //Check if number < 0, Save this info in variable sign and make the number positive
    if(num<0)
    {
        sign = -1;
        num = num*-1;
    }
    
    //Extract each digit from right and add comma after every 3 digits.
    while(num>0)
    {
        count++;
        if(count >1 && (count%3 ==1))
        text[i++] = ',';
        
        text[i++] = '0' + num%10;
        num=num/10;
        
    }
    
    //Add '-' if number was negative.
    if(sign == -1)
        text[i++] = '-';
    
    //Add null terminator
    text[i] = '\0';
   
    //Reverse string before returning 
    int len = strlen(text);
    for(int i=0;i<(len/2);i++)
    {
        char temp = text[i];
        text[i] = text[len-i-1];
        text[len-i-1] = temp;
    }
    
    return text;
}

Implement isNumber()

The code is similar to atop but here we also need to check if number is a double. We need to make sure that the string has at most one decimal point.
The key steps in writing an isNumber function are:

• Check for sign(-) after we've checked for whitespace
• Check if each character lies between 0 & 9
• Make note of first decimal encountered.
• Return false if we encounter a second decimal point
• Return false as soon as we see a non numeric character
• Return true otherwise.

bool isNumber(string toTest)
{
    int index =0, decimal = 0;

    //Checking for sign
    if(toTest[index] == '-')
        index++;
    
    while(index<toTest.length())
    {
        int num = toTest[index] - '0';

        //Check for numerical digit
        if(num >=0 && num <=9)
        {
            index++;
            continue;
        }

        //Check if character is a decimal point and if its the first decimal point.
        else if(toTest[index] == '.')
        {

            //Number cannot have 2 decimal points so return false.
            if(decimal)
                return false;
            else
                decimal = 1;
            index++;
        }
        else
        return false;
    }
    return true;
}

Implement strtok()

strtok takes in a string and one or more tokens, and it returns a substring which is split using all the tokens provided. The tricky part is that once you call strtok with a string, next time you can call it and pass NULL instead of any string and it will assume the string you passed in previous call.
The key steps in writing an atoi function are:

• Make a static copy of the string passed into the function for reuse on next function call.
• If new string is passed to function, make a copy of it else reuse the last sent string.
• Check for tokens in the string to split on. Make sure to keep track of end of string.
• Update the saved copy of string as well as the string passed into the function.

char* new_strtok(char* str, const char* tokens)
{
    //Making a static string to be used again on next function call.
    static char *temp;
    
    //If string passed to function is not null, copy it to our static variable
    if(str!=NULL)
    {
        temp=(char*)malloc(strlen(str));
        strcpy(temp,str);
    }

    //If the string passed is NULL and even the copy is NULL, we are done and return NULL.
    else if(temp==NULL)
    return NULL;

    //If only the string passed is NULL and the copy still has data, work with it.
    else
    {
        str=temp;
    }

    int chars=0, len = strlen(tokens), flag=0;
    
    //Run the loop till we find a token or our copy is fully parsed.
    while(*temp)
    {
        for(int i=0;i<len;i++)
        {
            if(*temp==tokens[i])
            {
                if(chars==0)
                {
                    flag=1;
                    str++;
                }
                else
                {
                    temp++;
                    str[chars]='\0';
                    return str;
                }
            }
        }
        if(flag==0)
            chars++;
        temp++;
        flag=0;
    }
    temp=NULL;
    str[chars]='\0';
    return str;
}

Implement atoi()

The key steps in writing an atoi function are:

• Check for whitespace at the start of the string
• Check for sign(-) after we've checked for whitespace
• Check if each character lies between 0 & 9
• Break as soon as we see a non numeric character
• Make sure to multiply by sign before returning result

int atoi(const char *text)
{
    if(text==NULL || strlen(text)==0)
    return 0;
    
    int len = strlen(text), i = 0, sign = 1, num = 0;
    
    //Checking for whitespace
    while(text[i] == ' ' || text[i] == '\t' || text[i] == '\n')
    i++;
    
    //Checking for sign
    if(text[i] == '-')
    {
        sign=-1;
        i++;
    }
    
    //Checking for numeric characters
    while(i<len)
    {
        if((text[i] - '0') >=0 && (text[i] - '0') <=9)
        {
            num = num*10 + (text[i] -'0');
            i++;
        }
        //Stopping when we see non numeric character
        else
        break;
    }
    
    // multiply the number by sign before returning
    return num*sign;
}