Java Solution, boolean array


  • 30

    Use a boolean array to mark if character at each position is bold or not. After that, things will become simple.

    public class Solution {
        public String addBoldTag(String s, String[] dict) {
            boolean[] bold = new boolean[s.length()];
            for (int i = 0, end = 0; i < s.length(); i++) {
                for (String word : dict) {
                    if (s.startsWith(word, i)) {
                        end = Math.max(end, i + word.length());
                    }
                }
                bold[i] = end > i;
            }
            
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if (!bold[i]) {
                    result.append(s.charAt(i));
                    continue;
                }
                int j = i;
                while (j < s.length() && bold[j]) j++;
                result.append("<b>" + s.substring(i, j) + "</b>");
                i = j - 1;
            }
            
            return result.toString();
        }
    }
    

  • 6

    You could replace your

                    i + word.length() <= s.length() 
                    && s.substring(i, i + word.length()).equals(word)
    

    with just

                    s.startsWith(word, i)
    

    which is much nicer and faster (your solution then gets accepted in about 35 ms instead of about 100 ms)


    After rewriting your first part a bit more:

        boolean[] bold = new boolean[s.length()];
        for (int i = 0, end = 0; i < s.length(); i++) {
            for (String word : dict)
                if (s.startsWith(word, i))
                    end = Math.max(end, i + word.length());
            bold[i] = end > i;
        }
    

    Two Python versions:

    def addBoldTag(self, s, dict):
        bold = [False] * len(s)
        for i in range(len(s)):
            length = max([len(word)
                          for word in dict
                          if s.startswith(word, i)] or [0])
            bold[i:i+length] = [True] * length
        it = iter(s)
        return ''.join('<b>' * k + ''.join(itertools.islice(it, len(list(g)))) + '</b>' * k
                       for k, g in itertools.groupby(bold))
    
    def addBoldTag(self, s, dict):
        def bold():
            end = 0
            for i in range(len(s)):
                for word in dict:
                    if s.startswith(word, i):
                        end = max(end, i + len(word))
                yield end > i
        it = iter(s)
        return ''.join('<b>' * k + ''.join(itertools.islice(it, len(list(g)))) + '</b>' * k
                       for k, g in itertools.groupby(bold()))

  • 0

    @StefanPochmann You are right, updated my post. Thanks!


  • 0
    J

    String.indexOf is your friend.


  • 1

    @shawngao said in Java Solution, boolean array:

        boolean[] bold = new boolean[s.length()];
        for (int i = 0, end = 0; i < s.length(); i++) {
            for (String word : dict) {
                if (s.startsWith(word, i)) {
                    end = Math.max(end, i + word.length());
                }
            }
            bold[i] = end > i;
        }
    

    Could you elaborate the code above? Why will bold represent the bold positions? It's not intuitive to understand...

    Thanks;)


  • 0

    @GoPhD Add some explanation in line. Hope that helps.

        for (int i = 0, end = 0; i < s.length(); i++) { // For every character in `s`,
            for (String word : dict) { // For every `word` in `dict`, we test:
                // If substring s[i, i + word.length()] == word, meaning characters between i, 
                // i + word.length() should be `bold`.
                if (s.startsWith(word, i)) {
                    // Use variable `end` to store known longest end of current continuous `bold` characters
                    end = Math.max(end, i + word.length());
                }
            }
            // If `end` > `i`, meaning character at position `i` is within the current continuous `bold`
            // characters, we mark it as `bold`.
            bold[i] = end > i;
        }
    

  • 0
    H

    c++ version

    string addBoldTag(string s, vector<string>& dict) {
            string ans = "";
            int n = s.length();
            bool isBold[s.length()];
            
            for(int i = 0, end = 0; i < n; i++){
                for(string word: dict){
                    int l = word.length();
                    if(i + l <= n && s.substr(i, l) == word)
                        end = max(end, i + l);
                }
                
                isBold[i] = end > i;
            }
            
            for(int i = 0; i < n; i++){
                if(!isBold[i]) ans += s[i];//ans.append(1, s[i]);
                else{
                    int j = i;
                    while (j < s.length() && isBold[j]) j++;
                    ans.append("<b>" + s.substr(i, j-i) + "</b>");
                    i = j - 1;
                }
            }
            
            return ans;
        }

  • 0
    H

    Same logic, different code here:

    public String addBoldTag(String s, String[] dict) {

        //Algo thinking: (1) get all the bold intervals, (2) merge
        //time = O(N^3), space = (N); N = s.length()
        
        boolean[] bold = new boolean[s.length()];
        for (String e: dict) {
            int len = e.length();
            for (int i = 0; i + len <= s.length(); i++) {
                if (s.substring(i, i + len).equals(e)) {
                    Arrays.fill(bold, i, i + len, true);
                }
            }
        }
        
        StringBuilder builder = new StringBuilder();
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i ++) {
            if ((i == 0 && bold[i]) || (bold[i] && !bold[i - 1])) builder.append("<b>");
            builder.append(c[i]);
            if ((i == c.length - 1 && bold[i]) || ( i < c.length - 1 && bold[i] && !bold[i + 1])) builder.append("</b>");
        }
        
        return builder.toString();
    }

  • 3
    Z

    Thank you for the solution! In C++, it seems string.find() is faster than string.substr() == dict. It improves the run time from 60-100ms to 19ms.

    class Solution {
    public:
        string addBoldTag(string s, vector<string>& dict) {
            int n = s.size();
            vector<int> mp(n, 0);
            for (string sd:dict) {
                int m = sd.size(), p = -1;
                while (true) {
                    p = s.find(sd, p+1);
                    if (p == -1) break;
                    for (int j = p; j < p+m; ++j) mp[j] = 1;
                }
            }
            string ans;
            for (int i = 0; i < n;) {
                if (mp[i]) {
                    ans += "<b>";
                    while (i < n && mp[i]) ans += s[i++];
                    ans += "</b>";
                }
                else {
                    while (i < n && mp[i] == 0) ans += s[i++];
                }
            }
            return ans;
        }
    };
    

  • 0
    F

    Very clear, thx.


  • 0

    Very clever, thank you for sharing!!!


  • 0
    C

    @zestypanda Nice prompt! Up Vote!


  • 0
    W

    Thank you for your code!


  • 0
    M

    Nice solution! A nitpick:

    result.append("<b>" + s.substring(i, j) + "</b>");
    

    Why not take advantage of StringBuilder since we're already using it? So change it to:

    result.append("<b>").append(s.substring(start, end)).append("</b>");
    

Log in to reply
 

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