Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Solution:

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {

       ListNode  *fast , *slow;
       fast=slow=head;
       for(int i=0; inext;
       if (fast==NULL) return head->next;
       else{
           while(fast->next!=NULL){
               fast=fast->next;
               slow=slow->next;
           }
           slow->next=slow->next->next;
       }
       return head;
    }
};

Not much to explain here.

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

This is the simple solution.
  
class Solution {
public:
    string longestCommonPrefix(vector &strs) {
 
         if(strs.size() == 0) return "";

        int num = strs.size();
        int len = strs[0].size();

        for(int j = 0; j            for(int i = 1; i                 if(strs[i][j]!=strs[i-1][j]){
                    return strs[0].substr(0,j);
                }
            }
        }
        return strs[0];    
    }
};

We have a string vector containing different strings. We start off with first letter of string (j=0).
 The other loop starts at i=1 pointing to the string at index 1 in the vector.
The outer loop is for iterating through particular j for all the strings.
In the first iteration of the inner loop i=1, j=0;
strs[1][0] refers to first character of the string at index 1.
strs[0][0] refers to the first character of the string at index 0.
Both of them are compared. If found unequal we return the substring strs[0].substr(0,0) which basically is null here.
In the second iteration of the inner loop i=2, j=0;
strs[2][0] (first character of the string at index 2) is compared with strs[1][0] (first character of string at index 1). Similarly we iterate through all the strings (i) comparing their first characters with the first character of the previous string (i-1).
Then the outer loop is incremented (we compare all strings for their second characters) and proceed so on.
In the worst case the complexity will be O(n².

Integer to Roman

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Solution:
We take two arrays containing the special cases. Since the number will not be greater than 3999, we need to know the Roman representations of up to he number 1000.
M = 1000
D = 500
C = 100
L = 50
X = 10
V = 5
I = 1

Here's the code. I got it from the comments on the Leetcode's problem page. Concise and precise.

class Solution {
public:
    string intToRoman(int num) {
        string result;
        int newnum;
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        for(int i =0; i<13;i++)
        {
            newnum = num/values[i];
             num = num-newnum*values[i];
            while(newnum--)
            {
                result.append(symbols[i]);
            }
      
        }
        return result;
    }
};

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

This is a classic problem involving Catalan numbers.
Catalan numbers is calculated using 

Catalann = (1/n+1)2nCn

There are many counting problems in combinatorics whose solution is given by the Catalan numbers.

• C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's . For example, the following are the Dyck words of length 6:

        XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

         ((()))     ()(())     ()()()     (())()     (()())

 

In our case for n =3, we get 5 combinations as can be calculated.

 

We solve this problem using recursion. The basic idea is we keep 2 stocks of parentheses. Open and  Close. 

The combinations are made by picking parentheses from these stocks. When both these stocks are empty, we end up with one particular combination. We store it in our string vector and the recursion lets us find other combinations. Here's the code for it : 

  

class Solution {
public:
    vector generateParenthesis(int n) {

      vector ans;
      if (n>0) brackets(ans, "", n, 0);
      return ans;  

    }

    void brackets(vector & ans, string s, int openStock,  int closeStock) {
    if (openStock==0 && closeStock==0) ans.push_back(s);
 
   if(openStock>0) brackets(ans, s+"(", openStock-1, closeStock+1);
   if(closeStock>0) brackets(ans, s+")", openStock, closeStock-1);
}
};  

To understand, try dry run for n =2. It will help you understand better. 

Palindrome number

Determine whether an integer is a palindrome. Do this without extra space. 
Solution : 
Code:

class Solution {

public:

    bool isPalindrome(int x) {

        if(x<0) return false;

    int div = 1;

    while(x/div>=10)

    {

        div=div*10;

    }

    while(x!=0)

    {

        int l = x/div;

        int r = x%10;

        if(l!=r) return false;

        x = (x%div)/10;

        div/=100;

    }

    return true;

    }   

};

String to Integer (atoi)

Implement atoi to convert a string to an integer.
Solution : 
Code:

class Solution {

public:

    int atoi(const char *str) {

      

       if (*str =='\0') return 0;

       // skip whitespaces.

       while ((*str) == ' ') str++;

       // sign

       int sign = 1;

       if(*str == '-')

       {

            sign = -1;

            str++;

       }

       else if(*str == '+')

       {

           sign = 1;

           str++;

       }

       // convert to number

       int num = 0;

       while (isdigit(*str))

       {

            if(((num == 214748364) && ((*str) - '0' >7)) || (num > 214748364))

            return (sign>0? INT_MAX : INT_MIN);

            num = num*10 + ((*str)-'0');

            str++;

       }

       return (sign*num);

    }

};

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. 
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

 bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

A good explanation from the official leetcode site can be found here

It is somewhat easy to think of an algorithm for most of the cases except for patterns which have a .* .
For eg :
s = "abcbcd" ; p ="a.*c.*cd"
Here, ".*" in p means repeat '.' 0 or more times. 
Since '.' can match any character, it is not clear how many times '.' should be repeated. Should the 'c' in p matches the first or second 'c' in s? Unfortunately, there is no way to tell without using some kind of exhaustive search.
Here is the algorithm presented by leetcode. It's short but do devote ample time going through it, lest you overlook some test cases. 

Code:
    bool isMatch(const char *s, const char *p) {  
            assert(s && p);
    if (*p == '\0') return *s == '\0';

    // next char is not '*': must match current character
    if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
    }
    // next char is '*'
    while ((*p == *s) || (*p == '.' && *s != '\0')) {
        if (isMatch(s, p+2)) return true;
        s++;
    }
    return isMatch(s, p+2);
    }