easy java solution with explanation beats 80%


  • 1
    public String addBoldTag(String s, String[] dict) {
            StringBuilder res = new StringBuilder(s);
            int n = s.length();
            // use boolean[] inDict   to record which char in the string is contained in at least one dict word
            boolean[] inDict = new boolean[n];
            StringBuilder sb = new StringBuilder(s);
            for(String word : dict) {
                int index = sb.indexOf(word);
                while(index != -1) {
                    sb.setCharAt(index,' ');
                    for(int i = 0; i < word.length(); i++) {
                        inDict[i + index] = true;
                    }
                    index = sb.indexOf(word);
                }
                sb = new StringBuilder(s);
            }
            // use st to record how the insert index is affected by <b>(3 chars) and </b>(4 chars)
            int i = 0, j = 0,st = 0;
            while(i < n && j < n) {
                while(i < n && !inDict[i]) i++;
                if(i == n) break;
                j = i + 1;
                while(j < n && inDict[j]) j++; 
                res.insert(i + st,"<b>");
                res.insert(j + st + 3,"</b>");
                i = j + 1;
                st += 7;
            }
            return res.toString();
        }

  • 1
    L

    Good solution.


  • 1

    @lyq0930 thanks


Log in to reply
 

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