[LintCode] Add and Search Word

Design a data structure that supports the following two operations:addWord(word) and search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or ..

A . means it can represent any one letter.

Example

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

Note

You may assume that all words are consist of lowercase letters a-z.

class Trie {
    unordered_map<char,Trie*> _map;
    bool _end;
public:
    Trie() {
        _end = false;
    }
    void add(string &s,int n) {
        if(!_map.count(s[n])) {
            _map[s[n]] = new Trie();
        }
        if(n == s.length() - 1) {
            _map[s[n]]->_end = true;
        } else {
            _map[s[n]]->add(s, n+1);
        }
    }
    
    bool search(string &s, int n){
        if(s.length() -1 == n) {
            if(s[n] == '.') {
                for(auto e : _map) {
                    if(e.second->_end) return true;
                }
                return false;
            }
            return _map.count(s[n]) ? _map[s[n]]->_end : false;
        }
        if(s[n] == '.') {
            for(auto e : _map) {
                if(e.second->search(s, n+1)) {
                    return true;
                }
            }
        } else {
            if(!_map.count(s[n])) return false;
            return _map[s[n]]->search(s, n+1);
        }
        return false;
    }
};

class WordDictionary {
    Trie _trie;
public:
    void addWord(string word) {
        _trie.add(word, 0);
    }
    bool search(string word) {
        return _trie.search(word, 0);
    }
};

[LeetCode] Longest Common Prefix

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

class Solution {
    static bool comp(string &s1, string &s2) {
        return s1.length() < s2.length();
    }
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0) return "";
        sort(strs.begin(), strs.end(), comp);
        string s = strs[0];
        int len = s.length();
        for(int i=1;i<strs.size();i++) {

            while(strs[i].find(s.substr(0, len)) != 0) len --;
        }
        return s.substr(0, len);
    }
};

[LeetCode] String to Integer (atoi)

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.

class Solution {
public:
    int myAtoi(string str) {
        if(str.empty()) return 0;
        int i = 0;
        bool hasPlus = false;
        while(i<str.length() && str[i] == ' ') i++;
        
        if(i<str.length() && str[i] == '+') {
            i++;
            hasPlus = true;
        }
        int flag = 1;
        if(!hasPlus && i < str.length() && str[i] == '-') 
        {
            flag = -1;
            i++;
        }

        long res = 0;
        
        while(i<str.length())
        {
            if(!isdigit(str[i]) ) return res*flag;
            res = res*10 + str[i] - '0';
            if(res > INT_MAX)
            {
                if(flag == 1) return INT_MAX;
                if(res != (long)-1*INT_MIN ) return INT_MIN;
            }
            i++;
        }
        
        return res * flag;
    }
};

[LintCode] Space Replacement

Write a method to replace all spaces in a string with %20. The string is given in a characters array, you can assume it has enough space for replacement and you are given the true length of the string.

Example

Given "Mr John Smith", length = 13.

The string after replacement should be "Mr%20John%20Smith".

Analysis: We can know the length after the replacement. And then we just need to fill in the new space from end to beginning of the word.

class Solution {
public:
    int replaceBlank(char string[], int length) {
        if(0==length) return 0;
        int num = 0;
        for(int i=0;i<length;i++){
            if(string[i] == ' ') num++;
        }
        
        int newLen = length + num*2;
        string[newLen] = 0;
        int j = 1;
        for(int i=length-1;i>=0;i--){
            if(string[i] != ' '){
                string[newLen - j] = string[i];
                j++;
            }
            else{
                string[newLen - j] = '0';
                j++;
                string[newLen - j] = '2';
                j++;
                string[newLen - j] = '%';
                j++; 
            }
        }
        return newLen;
    }
};  

[LintCode] Delete Digits

Given string A representative a positive integer which has Ndigits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example

Given an integer A = "178542", k = 4

return a string "12"

class Solution {
public:
    string DeleteDigits(string A, int k) {
        if(A.length() < k) return A;

        int j = 0;
        while(j < A.length()-1 && k > 0)
        {
            if(A[j]>A[j+1]){
                A.erase(j,1);
                k--;     
                if(j>0)j--;
            }
            else j++;
        }
        A = A.substr(0, A.length()-k);
        int index = A.find_first_not_of("0");
        return A.substr(index);
    }
};

[LintCode] Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is"ABC"

class Solution {
public:    
    string longestCommonPrefix(vector<string> &strs) {
        int len = strs.size();
        string res;
        if(0 == len) return res;
        int index = 0;
        
        while(index<strs[0].length())
        {
            for(int i=1;i<len;i++)
            {
                if(strs[i][index] != strs[0][index]) 
                {
                    return strs[0].substr(0, index);
                }
            }
            index++;
        }
        return strs[0];
    }
};

[LeetCode] 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:
    string multiply(string num1, string num2) 
    {
        string res(num1.size()+num2.size(), '0');
        for (int i=num1.size()-1;i>=0;i--) 
        {
            int overflow = 0;
            for (int j=num2.size()-1;j>=0;j--) 
            {
                int sum = res[i+j+1]-'0' + (num1[i]-'0')*(num2[j]-'0') + overflow;
                res[i + j + 1] = sum%10 + '0';
                overflow = sum/10;
            }
            res[i] += overflow;
        }
    
        size_t t = res.find_first_not_of("0");
        if (string::npos == t) return "0";
        return res.substr(t);
    }
    
};

[LeetCode/LintCode] 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(string s) {
        int len = s.length();
        int i=len-1;
        while(s[i] == ' ')i--;
        int p = i;
        for(;i>=0;i--) if(s[i] == ' ') break;
        return p-i;
    }
};

[LeetCode] Longest Substring Without Repeating Characters

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.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.length();
        int len = 0, first = 0, start = 0, end = size - 1;
        vector<int> set(128,-1);
        while(start <= end)
        {
            if(set[s[start]] >= first)
            {
                len = max(len, start-first);
                first = set[s[start]] + 1;
            }
            set[s[start]] = start++; 
        }
        return max(len, start-first);
    }
};