Java fragment solution


  • 0
    D

    First we fragment the given string into multiple continuous segments. Second we record the lengths we have met for each character. For example, after we process abcd, we have met a with length 4. Third, scan each segment's characters, then we get the solution.

    public class Solution {
        public int findSubstringInWraproundString(String p) {
            if (p == null || p.length() == 0) {
                return 0;
            }
            List<String> segments = fragment(p);
            Map<Character, Integer> metlengths = new HashMap<>();
            int substrings = 0;
            for (String segment : segments) {
                for (int i = 0; i < segment.length(); i++) {
                    char ch = segment.charAt(i);
                    int metlength = metlengths.containsKey(ch) ? metlengths.get(ch) : 0;
                    substrings += Math.max(0, segment.length() - i - metlength);
                    metlengths.put(ch, Math.max(segment.length() - i, metlength));
                }
            }
            return substrings;
        }
    
        private List<String> fragment(String p) {
            List<String> strs = new ArrayList<>();
            int lastEnd = -1;
            while (lastEnd + 1 < p.length()) {
                StringBuffer sb = new StringBuffer();
                sb.append(p.charAt(lastEnd + 1));
                int candidate = lastEnd + 2;
                for (; candidate < p.length(); candidate++) {
                    char ch1 = p.charAt(candidate - 1);
                    char ch2 = p.charAt(candidate);
                    if ((ch2 == ch1 + 1) || (ch1 == 'z' && ch2 == 'a')) {
                        sb.append(ch2);
                    } else {
                        break;
                    }
                }
                lastEnd = candidate - 1;
                strs.add(sb.toString());
            }
            return strs;
        }
    }
    

Log in to reply
 

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