[Leetcode] Longest Common Prefix

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

Analysis:
Compare each character in first string to all others, return the sub string that is matching all strings.

Solution:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        
     
        string first;
        
        if(strs.size() == 0)
        {
            return first;
        }
        
        first = strs[0];
        
        if(strs.size() == 1)
        {
            return first;
        }
        
        int len = 0;
        bool loop_break = false;
        
        for(int i = 0; i < first.size(); i++)
        {
            for(int j = 1; j < strs.size(); j++)
            {
                if(i < strs[j].size())
                {
                    // find mismatch on ith character, break the loop
                    if(first[i] != strs[j][i])
                    {
                        loop_break = true;
                        break;
                        
                    }

                }
                else
                {
                    // find a string of length that is less than i, break the loop
                    loop_break = true;
                    break;
                }
            }
            
            // no loop break, meaning ith character is matching in all strings
            if(loop_break == false)
              len++;
     
            else
              break;
            
        }
        
        return first.substr(0, len);
        
    }
};

[Leetcode] Restore IP addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Analysis:
The problem assumes input is an IPv4 address, wnhich has four octets and each of them is a non-negative number less than 256.
Idea is to scan the string from left to right, whenever we found a octet, if total found octets are still less than 4, check if any more valid octets can be found from right substring. We can validate the length of right substring and how many octets we have left before jumping into it.

Solution:

class Solution {
public:

  // Check if string s is a valid IP address
  bool is_valid(string s)
    {
    if (s.size() > 3) return false;
        if (s.size()==3)
        {   
        if(atoi(s.c_str())>255 || atoi(s.c_str())==0 || s[0] == '0')
              return false;
        } 
        if (s.size()==2)
        {
        if(atoi(s.c_str())==0 || s[0] == '0')
         return false;
        }
        return true;
    }
    
    void findAllIPs(string s, int index, int len, vector<string> & result, string &octet, int num)
    {
        if(num == 0 && index != len)
           return;
           
        if(index == len)
        {
        cout<<"find one IP: "<<octet<<endl;
            result.push_back(octet);
            return;
        }
        
        string temp;
        
        for(int i = index; i < len; i++)
        {
             temp = s.substr(index, i - index + 1);
             // proceed if sub string temp is a valid IPv4 address
             // length of right substring is a possible match for left octets 
             if(is_valid(temp) && s.substr(i+1).size() <= 3 * (num-1) && s.substr(i+1).size() >= num - 1)
             {
                 string original = octet;
                 if(index !=0)
                 {
                   octet = octet + "." + temp;
                  
                 }
                 else
                 {
                  octet = temp;
                 }
            
                 num--;
                 findAllIPs(s, i+1 , len, result, octet, num);
                 num++;
                 
                 octet = original;
             }
             else
             {
              continue;
             }
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        
        vector<string> result;
        string octet;
        
        int len = s.size();
        
        // invalid string length, skip
        if(len < 4 || len > 12)
        {
            return result;
        }
        
        int num = 4;
        findAllIPs(s, 0, len, result, octet, num);
      
        return result;    
    }
};