Implement strStr()

Problem:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button  to reset your code definition.

Solution:
class Solution {
public:
    int strStr(string haystack, string needle) {
        int sol = - 1;
        int size = haystack.size(), size_ndl = needle.size();
        if (size_ndl > size)
            return sol;
        else if (size_ndl == 0)
            return 0;
            
        for (int i = 0; i < (size - size_ndl + 1); i++) {
            if (haystack[i] == needle[0]) {
                for (int j = 0; j < size_ndl; j++) {
                    if (haystack[i + j] != needle[j])
                        break;
                    else if (j == (size_ndl - 1) && haystack[i + j] == needle[j])
                        return i;
                }
            }
        }
        return sol;
    }
};

==== Second time ====
 bool check_need(string haystack, int index, string needle) {
            int j = 0;
            int need_size = needle.size();
         
            if (haystack.size() - index < need_size) {
                return false;
            }
            for (int i = index; i < haystack.size(); i++) {
                if (j == needle.size()) {
                    return true;
                }
                if (haystack[i] != needle[j++]) {
                    return false;
                }
            }
            return true;
        }
 
    int strStr(string haystack, string needle) {
        int need_size = needle.size();
        int hay_size = haystack.size();
        int ans = 0;
        if (hay_size < need_size) {
            return -1;
        }
     
        for (int i = 0; i < hay_size; i++) {
            if (haystack[i] == needle[0] &&
                check_need(haystack, i, needle)) {
                return i;
            }
        }
     
        if (need_size == 0) {
            return 0;
        } else {
            return -1;
        }
    }
=========
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == haystack || needle.empty()) {
            return 0;
        }
        if (haystack.empty() || needle.size() > haystack.size()) {
            return -1;
        }

        for (int i = 0; i <= haystack.size() - needle.size(); i++) {
            if (haystack[i] == needle[0] && haystack.substr(i, needle.size()) == needle) {
                return i;
            }
        }
        return -1;
    }
};

====================

class Solution {

public:

    int strStr(string haystack, string needle) {

        int ans = 0;

        if (needle.size() == 0) {

            return ans;

        }

        if (haystack.size() == 0 || needle.size() > haystack.size()) {

            return -1;

        }

        

        int iter = 0, checker = 0;

        while (iter <= haystack.size() - needle.size()) {

            int tmp = iter;

            while (checker < needle.size() &&

                   haystack[tmp + checker] == needle[checker]) {

                checker++;

            }

            if (checker == needle.size()) {

                return iter;

            }

            iter++;

            checker = 0;

        }

        return -1;

        

    }

};

Count and Say

Problem:

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

Solution:
class Solution {
public:
    // Runs in 6ms
    string generate (string s) {
        string sol;
        int size = s.size();
        if (size == 0)
            return "1";
        int count = 1;
        for (int i = 0; i < size - 1; i++) {
            if (s[i] == s[i + 1])
                count++;
            else {
                sol += to_string(count);
                sol.push_back(s[i]);
                count = 1;
            }
        }
        sol += to_string(count);
        sol.push_back(s[size - 1]);
            
        return sol;
    }
    /*   // Runs in 4ms
    string generate (string s) {
        stringstream sol;
        int size = s.size();
        if (size == 0)
            return "1";
        int count = 1;
        for (int i = 0; i < size - 1; i++) {
            if (s[i] == s[i + 1])
                count++;
            else {
                sol << count << s[i];
                //sol.push_back(s[i]);
                count = 1;
            }
        }
        sol << count << s[size - 1];
            
        return sol.str();
    } */
    
    string countAndSay(int n) {
        string sol;
        
        for (int i = 1; i <= n; i++) {
            sol = generate(sol);
        }
        return sol;
    }
};

========= Third attempt =========

string countAndSay(int n) {
        if (n < 1) {
            return "";
        }
       
        string prev = "1";
        string ans;
        for (int i = 2; i <= n; i++) {
            int count = 1;
            for (int j = 0; j < prev.size() - 1; j++) {
                if (prev[j] == prev[j + 1]) {
                    count++;
                } else {
                    ans += to_string(count) + string(1, prev[j]);
                    count = 1;
                }
            }
            ans += to_string(count) + string(1, prev[prev.size() - 1]);
            prev = ans;
            ans.clear();
        }
       
        return prev;
    }

Plus one

Problem:

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Solution:
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        vector<int> sol;
        
        int size = digits.size();
        int carry = 1;
        for (int i = size - 1; i >= 0; i--) {
            sol.push_back((digits[i] + carry) % 10);
            carry = (digits[i] + carry) / 10;
        }
        if (carry)
            sol.push_back(carry);
        reverse(sol.begin(), sol.end());
        return sol;
    }
};
===== Another approach =====
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1, size = digits.size(), i = size - 1;
        if (size == 0) {
            digits.push_back(carry);
            return digits;
        }
        while (carry) {
            if (i < 0) {
                digits.insert(digits.begin(), carry);
                return digits;
            }
            int temp = digits[i] + carry;
            digits[i--] = temp % 10;
            carry = temp / 10;
        }
        return digits;
    }
};

===== Another approach =====

class Solution { public:     vector<int> plusOne(vector<int> &digits) {         // Start typing your C/C++ solution below         // DO NOT write int main() function         if (digits[digits.size()-1]!=9){             digits[digits.size()-1]++;             return digits;         }else{             digits[digits.size()-1]=0;             int carry=1;                           for (int i=digits.size()-2;i>=0;i--){                 if (digits[i]!=9){                     digits[i]++;                     return digits;                 }else{                     digits[i]=0;                 }             }             vector<int> res(digits.size()+1,0);             res[0]=1;             return res;         }     } }; ================ class Solution { public: vector<int> plusOne(vector<int>& digits) { reverse(digits.begin(), digits.end()); int carry = 1; for (int& digit : digits) { int tmp = digit + carry; digit = tmp % 10; carry = tmp / 10; } if (carry != 0) { digits.push_back(carry); } reverse(digits.begin(), digits.end()); return digits; } };