short java solution


  • 5
    T
        public String addBoldTag(String s, String[] dict) {
            int n = s.length();
            int[] mark = new int[n+1];
            for(String d : dict) {
                int i = -1;
                while((i = s.indexOf(d, i+1)) >= 0) {
                    mark[i]++;
                    mark[i + d.length()]--;
                }
            }
            StringBuilder sb = new StringBuilder();
            int sum = 0;
            for(int i = 0; i <= n; i++) {
                int cur = sum + mark[i];
                if (cur > 0 && sum == 0) sb.append("<b>");
                if (cur == 0 && sum > 0) sb.append("</b>");
                if (i == n) break;
                sb.append(s.charAt(i));
                sum = cur;
            }
            return sb.toString();
        }
    

  • 0
    Z

    Great solution! I like the use of array mark[]. I will help improve the performance, although the big O may not change due to string comparison.


  • 0
    T

    Nice !!! Thanks for sharing!!!

    public class Solution {
        public String addBoldTag(String s, String[] dict) {
            int[] hash=new int[s.length()+1];
            for(String str:dict){
                int index=s.indexOf(str,0);
                while(index!=-1){
                    hash[index]++;
                    hash[index+str.length()]--;
                    index=s.indexOf(str,index+1);
                }
            }
            
            int sum=0;
            for(int i=0;i<hash.length;i++){
                sum+=hash[i];
                hash[i]=sum;
            }
            
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<s.length();i++){
                if(hash[i]==0){
                    sb.append(s.charAt(i));
                }else{
                    int j=i;
                    while(j+1<s.length()&&hash[j+1]!=0){
                        j++;
                    }
                    sb.append("<b>");
                    sb.append(s.substring(i,j+1));
                    sb.append("</b>");
                    i=j;
                }
            }
            
            return sb.toString();
        }
    }
    
    

Log in to reply
 

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