Alg.18 Underscorify Substring

2020-04-11

Word count: 371 | Reading time≈ 2 min

For this problem, we need to write a function to wrap every potential substring with underscores in the main string. Here is an example:

First, we need to get every exsiting substring’s position.

public static List<Integer[]> getLocation(String str, String substring) {
        int substringLen = substring.length();
        List<Integer[]> locations = new ArrayList<Integer[]>();
        int Idx = 0;
        while (Idx < str.length()) {
        // Find the start point of one substring 
            int curIdx = str.indexOf(substring, Idx);
            if (curIdx != -1) {
            // add this substring's start and end positions to the result list
                locations.add(new Integer[] {curIdx, curIdx + substringLen});
                Idx = curIdx + 1;
            } else {
                break;
            }
        }
        return locations;
    }

Then, we need to collapse the substring’s position collection.

public static List<Integer[]> collapse(List<Integer[]> locations) {
        if (locations.size() == 0) {
            return locations;
        }
        List<Integer[]> transLocations = new ArrayList<Integer[]>();
        transLocations.add(locations.get(0));
        Integer[] prev = transLocations.get(0);
        for (int i = 1; i < locations.size(); i++) {
            Integer[] cur = locations.get(i);
            if (cur[0] <= prev[1]) {
                prev[1] = cur[1];
            } else {
                transLocations.add(cur);
                prev = cur;
            }
        }
        return transLocations;
    }

Now, we can use underscores to wrap each substrings.

public static String underscorify(String str, List<Integer[]> locations) {
        int strIdx = 0;
        int locationsIdx = 0;
        boolean inBetween = false;
        List<String> finalString = new ArrayList<String>();
        int i = 0;
        while (strIdx < str.length() && locationsIdx < locations.size()) {
            if (strIdx == locations.get(locationsIdx)[i]) {
                finalString.add("_");
                inBetween = !inBetween;
                if (!inBetween) {
                    locationsIdx++;
                }
                i = i == 1? 0 : 1;
            }
            finalString.add(String.valueOf(str.charAt(strIdx)));
            strIdx++;
        }
        
        if (locationsIdx < locations.size()) {
            finalString.add("_");
        } else if (strIdx < str.length()) {
            finalString.add(str.substring(strIdx));
        }
        return String.join("", finalString);
    }
    
public static String underscorifySubstring(String str, String substring) {
    List<Integer[]> finalString = collapse(getLocation(str, substring));
    return underscorify(str, finalString);
  }

Time complexity: O(n+m)(length of the main string and the substring); Space complexity: O(n)

Donate

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.