Reverse String

Write a function that takes a string as input and reverse the same.

Example:

Given s = "hello", return "olleh".

Approach: The idea is to swap the last and the first characters till the middle is reached.

1 2 3 4 5 6 7 8 9 10 11

string reverseString(string &s) { int low = 0, high = s.length() - 1; while(low < high){ char t = s[low]; s[low] = s[high]; s[high] = t; low++; high--; } return s; }

Read More

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Approach:  The idea is to traverse the string from both ends while skipping the non-vowels characters from both ends.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

char* reverseVowels(char* s) { int low = 0, high = strlen(s) - 1; char c; while(low < high){ //move forward to skip consonant while(low < strlen(s) && tolower(s[low]) != 'a' && tolower(s[low]) != 'e' && tolower(s[low]) != 'i' && tolower(s[low]) != 'o' && tolower(s[low]) != 'u'){ low++; } //move backward to skip consonant while(low < high && tolower(s[high]) != 'a' && tolower(s[high]) != 'e' && tolower(s[high]) != 'i' && tolower(s[high]) != 'o' && tolower(s[high]) != 'u'){ high--; } if(low < high){ c = s[low]; s[low] = s[high]; s[high] = c; low++; high--; } } return s; }

Read More

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

bool isPalindrome(char* s) { int i, j, len; len = strlen(s); i = 0; j = len - 1; while(i < j){        // skip non alpha chars from start        while(i < len && !isalnum(s[i])){ i++; }         // skip non alpha chars from end        while(j >= 0 && !isalnum(s[j])){ j--; }         if(i < j && tolower(s[i]) != tolower(s[j])){ return false; }         i++; j--; } return true; }

Read More

67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100"

Approach : The idea is to start from the right and keep adding digits and forwarding carry (if any). Also, take care of the case when one of them gets exhausted. For that, keep adding zero to the other one and forward carry if required. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

string Solution::addBinary(string a, string b) { int lenA = a.length(), lenB = b.length(); int i = lenA - 1, j = lenB - 1; int carry = 0; stack<char> out; int sum = 0; while(i >= 0 || j >= 0){ if(i >= 0 && j >= 0){ //convert to int and add sum = a[i] - '0' + b[j] - '0' + carry; i--; j--; } else{ //string a is exhausted if(i < 0){ sum = b[j] - '0' + carry; j--; } //string b is exhausted else{ sum = a[i] - '0' + carry; i--; } } //setting the carry accordingly if(sum > 1){ carry = 1; }else{ carry = 0; } sum = sum % 2; //convert back to character char aChar = '0' + sum; out.push(aChar); } //for final carry if(carry){ out.push('1'); } string res = ""; //reverse the output while(!out.empty()){ res = res + out.top(); out.pop(); } return res; }

Here is the link to the ideone solution : http://ideone.com/o5r3Eq

Read More

14. Longest Common Prefix

Given an array of strings, the problem is to find out the longest common prefix of all the strings.

Return empty string if no common prefix exists.

Approach:
Use the brute force way approach to solve the problem. First find the shortest string (as the longest common prefix can be of at most this length), minLenStr, which takes O(n) time. Next, compare each string one by one with this minLenStr, and keep an variable which indicates the rightmost index of minLenStr, this loop takes O(mn) where m is the shortest length of all strings.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string out = "";
        if(strs.size() == 0 ){
            return out;
        }
        //find the minimum length string since the longest common prefix can't be more than that length
        string minLenStr = strs[0];
        for(int i = 1; i < strs.size(); i++){
            if(strs[i].length() < minLenStr.length()){
                minLenStr = strs[i];
            }
        }
        //loop over all string and match all the starting characters, update the maximum size possible based on the starting matching characters
        int end = minLenStr.length();
        for(int i = 0; i < strs.size(); i++){
            int j = 0;
            while(j < end){
                if(minLenStr[j] != strs[i][j]){
                    break;
                }
                j++;
            }
            //update the maximum possible size
            if(j < end){
                end = j;
            }
        }
        return minLenStr.substr(0, end);
    }
};

Here is the link to the ideone solution : http://ideone.com/CWFcI8

Read More

58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, for s = "Hello World", return 5.

Approach: The idea is to start traversing from the right (ignoring the right spaces if any) and continue till a space is not found. 

class Solution {
public:
    int lengthOfLastWord(string s) {
        int len = s.length();
        int i = len - 1, j = 0;
        while(s[i] == ' '){
            i--;
        }
        while(i >=0 && ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))){
            i--;
            j++;
        }
        return j;
    }
};

Here is the link to the ideone solution : http://ideone.com/pYNIG9

Read More