Leetcode: String to Integer (atoi) in C++

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solution:
int atoi(const char *str) {
        double result = 0;
        int len = strlen(str);
        int i = 0;
        int flag = true;
        while(i<len&&str[i]==' ')
             i++;
        if(i<len&&(str[i]=='-'||str[i]=='+'))
        {
           flag = str[i]=='-'?false:true;
           i++;
        }
        for(;i<len;i++)
        {
            if(str[i]<'0'||str[i]>'9'||str[i]==' ')
               break;
            result = 10*result+(str[i]-'0');
            if(result>INT_MAX&&flag)
               return INT_MAX;
            if(result-1>INT_MAX&&!flag)
               return INT_MIN;
        }
        if(!flag)
        result = -result;
        return result;
    }

Leetcode: Longest Substring Without Repeating Characters in C++

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
Solution:
int lengthOfLongestSubstring(string s) {
        vector<int> curmap(256,-1);
        int n = s.size();
        int curlen = 0;
        int maxlen = 0;
        int curstart = 0;
        for(int i=0;i<n;i++)
        {
            int current = curmap[s[i]];
            if(current==-1)
            {
               curmap[s[i]] = i;
               curlen++;
               if(maxlen<curlen)
                 maxlen = curlen;
            }
            else
            {
                while(curstart<=current)
                {
                    curmap[s[curstart]] = -1;
                    curstart++;
                }
                curlen = i-current;
                curmap[s[i]] = i;
            }
            
        }
        return maxlen;
    }

Leetcode: Longest Palindromic Substring in C++

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Solution:
void search(string& s, int& left, int& right, int curL, int curR)
    {
        while(curL>=0&&curR<s.size())
        {
                if(s[curL]!=s[curR])
                  break;
                curL--;
                curR++;
        }
        curL++;
        curR--;
        if(curR-curL>right-left)
        {
           left = curL;
       right = curR;
        }
    }
    string longestPalindrome(string s) {
        int maxlength = INT_MIN;
        int left  = 0;
        int right = 0;
        int pos = 0;
        while(pos<s.size()-1)
        {
            search(s, left, right,pos, pos);
            search(s, left, right,pos, pos+1);
            pos++;
        }
        return s.substr(left, right-left+1);
    }

Leetcode: Multiply Strings in C++

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.

Solution:

string multiply(string num1, string num2) {
       int s1 = num1.size();
       int s2 = num2.size();
       string result(s1+s2+1, '0');
       std::reverse(num1.begin(),num1.end());
       std::reverse(num2.begin(),num2.end());
       int digit1 = 0;
       int carry = 0;
       for(int i =0;i<s1;i++)
       {
           digit1 = num1[i] - '0';
           carry = 0;
           for(int j=0;j<s2;j++)
           {
               int digit2 = num2[j] - '0';
               int exist = result[i+j] - '0';
               result[i+j] = (digit1*digit2+exist+carry)%10 + '0';
               carry = (digit1*digit2+exist+carry)/10;
           }
           if(carry>0)
           {
               result[i+s2] = carry+'0';
           }
       }
       std::reverse(result.begin(),result.end());
       int start = 0;
       while(result[start]=='0'&&start<result.size()) // skip leading '0'
       {
           start++;
       }
       if(start == result.size())
       return "0";
       else
       return result.substr(start);
    }

Leetcode: Substring with Concatenation of All Words in Java

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Solution:
public ArrayList<Integer> findSubstring(String S, String[] L) {
        HashMap<String, Integer> Lmap = new HashMap<String, Integer>();
        HashMap<String, Integer> Smap = new HashMap<String, Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        int total = L.length;
        if(total==0)
        return result;
        for(int i=0;i<total;i++)
        {
            if(!Lmap.containsKey(L[i]))
            Lmap.put(L[i], 1);
            else
            {
                int k = Lmap.get(L[i]);
                Lmap.put(L[i], k+1);
            }
        }
        int len = L[0].length();
        for(int i=0;i<=S.length()-len*total;i++)
        {
            Smap.clear();
            int j = 0;
            for(;j<total;j++)
            {
                String s = S.substring(i+j*len, i+(j+1)*len);
                if(!Lmap.containsKey(s))
                    break;
                if(!Smap.containsKey(s))
                Smap.put(s, 1);
                else
                {
                    int k = Smap.get(s);
                    Smap.put(s, k+1);
                }
                if(Smap.get(s)>Lmap.get(s))
                    break;
            }
            if(j==total)
            {
                result.add(i);
            }
        }
        return result;
    }

Leetcode: Anagrams in Java

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Solution:
public ArrayList<String> anagrams(String[] strs) {
        int len = strs.length;
        HashMap<String, Integer> mymap = new HashMap<String, Integer>();
        ArrayList<String> result = new ArrayList<String>();
        for(int i=0;i<len;i++)
        {
            char[] cur = strs[i].toCharArray();
            Arrays.sort(cur);
            String sorted = new String(cur);
            if(mymap.containsKey(sorted))
            {
                if(mymap.get(sorted)!=-1)
                {
                    result.add(strs[mymap.get(sorted)]);
                    mymap.put(sorted,-1);
                }
                result.add(strs[i]);
            }
            else
            {
                mymap.put(sorted, i);
            }
        }
        return result;
    }

Leetcode: Add Binary in C++

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

For example,

a = "11"b = "1"Return "100".


Solution:
string addBinary(string a, string b) {
        int lenA = a.size()-1;
        int lenB = b.size()-1;
        int carry = 0;
        string result = "";
        while(lenA>=0||lenB>=0)
        {
            
            int cura = 0;
            if(lenA>=0)
            cura = a[lenA] - '0';
            int curb =0;
            if(lenB>=0)
            curb = b[lenB] - '0';
            int cur = cura+curb+carry;
            if(cur>1)
            {
                carry = 1;
                cur = cur - 2;
            }
            else
                carry = 0;
            result+=char('0' + cur);
            lenA--;
            lenB--;
        }
        if(carry>0)
        result+='1';
        int start = 0;
        int end = result.size()-1;
        while(start<end)
        {
            char tmp = result[start];
            result[start] = result[end];
            result[end] =tmp;
            start++;
            end--;
        }
        return result;
        
    }

Leetcode: Length of Last Word in C++

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.

Solution:

public int lengthOfLastWord(String s) {
        int pre = -1;
        int len = s.length();
        if(len==0)
        return 0;
        int p =0;
        int end = len-1;
        while(end>0&&s.charAt(end)==' ')
            end--;
        while(p<=end)
        {
            if(s.charAt(p)==' ')
              pre = p;
            p++;
        }
        return end - pre;
    }

Leetcode: Minimum Window Substring in C++

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,

S = "ADOBECODEBANC"T = "ABC"
If there is no such window in S that covers all characters in T, return the emtpy string "".

Minimum window is "BANC".

Note:

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:
string minWindow(string S, string T) {
        string result = "";
        int count =0;
        int len = T.size();
        int ToFind[256] = {0};
        int Current[256] = {0};
        for(int i=0;i<len;i++)
        {
            ToFind[T[i]]++;
        }
        int start = 0;
        int rstart = 0;
        int rend = S.size()-1;
        for(int i=0;i<S.size();i++)
        {
            if(ToFind[S[i]]==0)
            {
                continue;
            }
            Current[S[i]]++;
            if(Current[S[i]]<=ToFind[S[i]])
            {
                count++;
            }
            if(count == len)
            {
                while(ToFind[S[start]]==0||Current[S[start]]>ToFind[S[start]])
                {
                    if(Current[S[start]]>ToFind[S[start]])
                    Current[S[start]]--;
                    start++;
                }
                int window = i - start +1;
                if(window<rend- rstart+1)
                {
                    rstart = start;
                    rend = i;
                }
            }
        }
        if(count==len)
        result = S.substr(rstart, rend-rstart+1);
        return result;
    }

Leetcode: Longest Common Prefix in C++

Write a function to find the longest common prefix string amongst an array of strings.
Solution:
string longestCommonPrefix(vector<string> &strs) {
        if(strs.size()==0)
        return "";
        string result = strs[0];
        string tmp = "";
        for(int i=1;i<strs.size();i++)
        {
            int k=0;
            tmp = "";
            while(k<strs[i].size()&&k<result.size())
            {
                if(strs[i][k] == result[k])
                {
                    tmp+=result[k];
                }
                else
                    break;
                k++;
            }
            result = tmp;
            
        }
        return result;
    }

Leetcode: Palindrome Number in C++

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

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution:

bool isPalindrome(int x) {
        if(x<0)
        return false;
        int digit = 1;
        int tmp = x;
        while(x/digit>=10)
        {
        digit*=10;
        }
        while(x!=0)
        {
            if(x%10!=x/digit)
            return false;
            else
            {
                x = x%digit;
                x = x/10;
                digit = digit/100;
            }
        }
        return true;
    }