java solution - no built-in string function


  • 0
    Y

    sometimes the interviewer doesn't want you to use the built-in string function or regex for whatever reasons

    the only string function being used here is toCharArray, obviously we have to get to char through charArray or charAt:

    public class Solution {
        public boolean splitV4(char[] IP, char delimiter, int cnt){
            int j = 0, i = 0, n = 0, parts = 0;
            for(;i<=IP.length;i++){
                char cur = (i==IP.length?delimiter:IP[i]);
                if(cur!=delimiter){
                    if(cur<'0' || cur>'9') return false;
                    else n = n*10 + cur - '0';
                }else{
                    if(i-j<1 || i-j>3) return false;
                    if(IP[j]=='0' && i-j>1) return false;//leading zero
                    if(n>255) return false;
                    j = i+1;
                    n = 0;
                    parts++;
                }
            }
            return parts==cnt;
        }
        public boolean splitV6(char[] IP, char delimiter, int cnt){
            int j = 0, i = 0, parts = 0;
            for(;i<=IP.length;i++){
                char cur = (i==IP.length?delimiter:IP[i]);
                if(cur!=delimiter){
                    if((cur>='0' && cur<='9') || (cur>='a' && cur<='f') || (cur>='A' && cur<='F'));
                    else return false;
                }else{
                    if(i-j<1 || i-j>4) return false;
                    j = i+1;
                    parts++;
                }
            }
            return parts==cnt;
        }
        public String validIPAddress(String IP){
            if(IP!=null && IP.length()>0){
                if(splitV4(IP.toCharArray(),'.',4)) return "IPv4";
                if(splitV6(IP.toCharArray(),':',8)) return "IPv6";
            }
            return "Neither";
        }
    }
    

    This method pretty much implements the java built-in split function in a customized way. From the performance POV, we only need one time linear search of the IP string checking IPv4/IPv6 validity(with built-in split, there're two times linear search).

    for comparison, this is the java built-in split method:

        public String[] split(String regex, int limit) {
            /* fastpath if the regex is a
             (1)one-char String and this character is not one of the
                RegEx's meta characters ".$|()[{^?*+\\", or
             (2)two-char String and the first char is the backslash and
                the second is not the ascii digit or ascii letter.
             */
            char ch = 0;
            if (((regex.value.length == 1 &&
                 ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
                 (regex.length() == 2 &&
                  regex.charAt(0) == '\\' &&
                  (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
                  ((ch-'a')|('z'-ch)) < 0 &&
                  ((ch-'A')|('Z'-ch)) < 0)) &&
                (ch < Character.MIN_HIGH_SURROGATE ||
                 ch > Character.MAX_LOW_SURROGATE))
            {
                int off = 0;
                int next = 0;
                boolean limited = limit > 0;
                ArrayList<String> list = new ArrayList<>();
                while ((next = indexOf(ch, off)) != -1) {
                    if (!limited || list.size() < limit - 1) {
                        list.add(substring(off, next));
                        off = next + 1;
                    } else {    // last one
                        //assert (list.size() == limit - 1);
                        list.add(substring(off, value.length));
                        off = value.length;
                        break;
                    }
                }
                // If no match was found, return this
                if (off == 0)
                    return new String[]{this};
    
                // Add remaining segment
                if (!limited || list.size() < limit)
                    list.add(substring(off, value.length));
    
                // Construct result
                int resultSize = list.size();
                if (limit == 0) {
                    while (resultSize > 0 && list.get(resultSize - 1).length() == 0) {
                        resultSize--;
                    }
                }
                String[] result = new String[resultSize];
                return list.subList(0, resultSize).toArray(result);
            }
            return Pattern.compile(regex).split(this, limit);
        }
    

Log in to reply
 

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