Simple JAVA recursive solution


  • 0
    C
    public class Solution {
        
        List<String> list = new ArrayList<String>();
        
        public List<String> restoreIpAddresses(String s)
        {
            if(null != s && s.length() >= 4)
            {
                traverse(s, "", 0, 0);
                return list;
            }
            
            return list;
            
        }
        
        public void traverse(String s, String newString, int index, int depth)
        {
            if(depth == 3)
            {
                if(index > s.length() - 1 || s.substring(index).length() > 3 || (s.charAt(index) == '0' && s.substring(index).length() > 1))
                {
                    return;
                }
                else
                {
                    if(Integer.parseInt(s.substring(index)) <= 255)
                    {
                        list.add(newString + s.substring(index));
                    }
                }
                
            }
            
            for(int i = index; i < index + 3 && i < s.length(); i++)
            {
                if(i == index && s.charAt(i) == '0')
                {
                    traverse(s, newString + s.substring(index, i + 1) + ".", index + (i - index + 1), depth + 1);
                    break;
                }
                
                if(Integer.parseInt(s.substring(index, i + 1)) <= 255)
                {
                    traverse(s, newString + s.substring(index, i + 1) + ".", index + (i - index + 1), depth + 1);
                }
                else
                {
                    break;
                }
                
            }
            
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.