Palindrome Partitioning II (to optimize)

/*

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

*/
class Solution {
public:
    bool isPalindrome(string s){
      int size = s.length();
      int i=0;
      int j=size-1;
      while(i<j){
        if(s[i]!=s[j]) return false;
        i++;
        j--;
      }
      return true;
    }
   
    int findMinCut(string s, int pos){
       if(pos==0) return 0;
      
       char curr = s[pos];
       int found;
      
       int i=0;
       string newString = s.substr(i,pos-i);
       int result = findMinCut(s, pos-1)+1;
       while(newString.find(curr)!=string::npos){
            found = newString.find(curr);
            if(isPalindrome(newString.substr(found+1))){
              if((found+i)==0) result = 0;
              else result = min(result, findMinCut(s, i+found-1)+1);
            }
            i = found+1+i;
            newString = s.substr(i,pos-i);
       }
       return result;
    }
   
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = s.length();
        if(size<=0) return 0;
        return findMinCut(s, size-1);
    }
   
    };

Length of Last Word

/*

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,
Given s = "Hello World",
return 5.

*/
class Solution {
public:
    int lengthOfLastWord(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s[0]==NULL) return 0;
        int i = 0;
        int posLastSpace = -1;
        int posFirstSpace = -1;
        int posWord = -1;
        if(s[0]!=' ') posWord = 0;
        while(s[i]!=NULL){
           if(s[i]==' ') posFirstSpace = i;
           while(s[i]==' '){
             posLastSpace = i;
             i++;
             if(s[i]!=NULL && s[i]!=' ') posWord = i;
           }
           if(s[i]!=NULL) i++;
        }
       
        if(s[i-1]==' '){
          if(posWord!=-1) return posFirstSpace-posWord;
          return 0;
        }
        else return i-posWord;
    }
};

Decode Ways

/*

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

*/
class Solution {
public:
    bool isValidNumber(char c){
      return (!(c < '0' || c >'9'));
    }
   
    int numDecode(string s, int pos){      
        if(pos==0){
          return 1;
        }
       
        if(pos==1){
          if(s[0]>'2' || (s[0]=='2' && s[1]>'6') || s.substr(0, pos+1)=="10") return 1;
          else return 2;
        }
       
        if(s[pos]=='0') return numDecode(s, pos-2);
       
        int num = numDecode(s, pos-1);
       
        if(s[pos-1]=='0' || s[pos-1]>'2' || (s[pos-1]=='2' && s[pos]>'6')){
          return num;
        }
       
        num = num + numDecode(s, pos-2);
        return num;
    }
   
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        //validate the input string
        int size = s.length();
        if(size==0) return 0;
        int i;
        //validate the input
        for(i=0; i<size; i++){
          if(!isValidNumber(s[i])) return 0;
          if(s[i]=='0'){
            if(!(i>=1 && s[i-1]=='1')) return 0;
          }
        }
       
        return numDecode(s, size-1);
    }
};

Search a 2D Matrix

/*

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

*/
class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rowSize = matrix.size();
        if(rowSize == 0) return false;
        int colSize = matrix[0].size();
        if(colSize == 0) return false;
       
        if(target<matrix[0][0] ||  target>matrix[rowSize-1][colSize-1]) return false;
        if(target==matrix[0][0] || target==matrix[rowSize-1][colSize-1]) return true;
       
        int low = 0;
        int high = rowSize - 1;
        int mid = (low+high)/2;
        int midVal;
        if(target == matrix[mid][0]) return true;
               
        while(matrix[mid][0] != target && low <= high && mid >=0 && mid < rowSize){
          midVal = matrix[mid][0];
          if(target > midVal) low = mid+1;
          if(target == midVal) return true;
          if(target < midVal) high = mid-1;
          mid = (low+high)/2;
        }
       
        if(matrix[mid][0] == target) return true;
        int row;
        if(target>matrix[rowSize-1][0]) row = rowSize-1;
        else if(low>rowSize-1) row = high;
        else if(target>matrix[high][0] && target<matrix[low][0]) row = high;
       
        low = 0;
        high = colSize - 1;
        mid = (low+high)/2;
        if(matrix[row][mid] == target) return true;
        if(matrix[row][high] < target) return false;
       
        while(matrix[row][mid] != target && low <= high){
          midVal = matrix[row][mid];
          if(target > midVal) low = mid+1;
          if(target == midVal) return true;
          if(target < midVal) high = mid-1;
          mid = (low+high)/2;
        }
       
        if(matrix[row][mid]==target) return true;
       
        return false;
    }
};

Set Matrix Zeroes

/*

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

*/
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rowSize = matrix.size();
        if(rowSize == 0) return;
        int colSize = matrix[0].size();
        if(colSize == 0) return;
       
        int i, j;
        int k;
        int impossibleValue = -10000;
       
        for(i=0; i<rowSize; i++){
          for(j=0; j<colSize; j++){
            if(matrix[i][j]==0){
             matrix[i][j] = impossibleValue;
            }
          }
        }
       
        for(i=0; i<rowSize; i++){
          for(j=0; j<colSize; j++){
            if(matrix[i][j] == impossibleValue){
              for(k=0; k<colSize; k++){
                 if(matrix[i][k]!=impossibleValue)
                 matrix[i][k] = 0;
              }
              for(k=0; k<rowSize; k++){
                 if(matrix[k][j]!=impossibleValue)
                 matrix[k][j] = 0;
              }
            }
          }
        }
       
        for(i=0; i<rowSize; i++){
         for(j=0; j<colSize; j++){
            if(matrix[i][j] == impossibleValue)
            matrix[i][j] = 0;
         }
        }
    }
};

Multiply Strings

/*

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

*/
class Solution {
public:
    vector<int> convertToDigit(string num){
        int size = num.length();
        char init = '0';
        vector<int> result;
        int digit;
        for(int i=0; i<size; i++){
            digit = num[i] - init;
            if(digit>9 || digit<0){
                result.clear();
                return result;
            }
            result.push_back(digit);
        }
        return result;
    }
    char convertToChar(int num){
       char init = '0';
       return init+num;
    }
  
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> left;
        vector<int> right;
        string result;
      
        left = convertToDigit(num1);
        right = convertToDigit(num2);
      
        vector<vector<int>> temp;
        vector<int> line;
        int i, j, k;
        int multi = 0;
        int higher = 0;
        for(i=0; i<right.size(); i++){
            line.clear();
            higher = 0;
            for(j=left.size()-1; j>=0; j--){
                multi = right[i]*left[j];
                line.insert(line.begin(), multi%10 + higher);
                higher = multi/10;
            }
            if(higher>0) line.insert(line.begin(), higher);
            else line.insert(line.begin(), 0);
            temp.push_back(line);
        }
      
        int sum;
        int plus = 0;
        int colSize = right.size();
        int rowSize = left.size()+1;
        for(k=colSize+rowSize-2; k>=0; k--){
            sum = 0;
            for(i=colSize-1; i>=0; i--){
              for(j=rowSize-1; j>=0; j--){
                if(i+j==k){
                   sum = sum + temp[i][j];
                   }
               }
            }
            sum = sum + plus;
            result.insert(0, 1, convertToChar(sum%10));
            plus = sum/10;
        }
       
        i=0;
        while(result[i]=='0'){
         i++;
        }
        if(i==result.size()) i = i-1;
       
        string substring = result.substr(i);
       
        return substring;
    }
};

Remove Element

/*

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

*/
class Solution {
public:
    void swap(int A[], int i, int j){
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0;
        int j = n-1;
        for(i=0; i<n && i<j; i++){
          if(A[i]==elem){
            while(A[j]==elem && j>=0 && i<=j) j--;
            if(j>=0 && i<=j){
            swap(A,i,j);
            j--;
            } else return i;
          }
        }
       
        if(i==j){
         if(A[i]==elem) return i;
         else return i+1;
        }
       
        if(j==-1) return 0;
       
        if(i==n) return n;
    }
};