String LeetCode Həllində qalın sözlər

Problem bəyanat

String LeetCode Həllində Qalın Sözlər – Açar sözlər sırası nəzərə alınmaqla words və simli s, bütün açar sözlərin bütün görünüşlərini düzəldin words[i] in s qalın. Aralarındakı hərflər <b> və </b> etiketlər qalın olur.

Qayıtmaq s qalın etiketləri əlavə etdikdən sonra. Qaytarılan sətir mümkün olan ən az sayda teqdən istifadə etməli və teqlər etibarlı olmalıdır birləşmə.Pin

misal

Test işi 1:

Input:

sözlər = [“ab”, “bc”]

s = “aabcd”

Çıxış:

" ab cd"

Izahat

“a a b c d” ifadəsini qaytarmağın asan olacağını düşünə bilərik. Ancaq daha çox etiket istifadə edərdi. Ancaq ən az sayda etiketdən istifadə etməliyik. Beləliklə, düzgün çıxış “a ab cd”dir.

Yanaşma

Fikir

1. boldMap bütün 0 ilə işə salın, qalın işarə üçün istifadə edin.
2. Hər sözü keçin və qalın Xəritə ilə qeyd edin.
3. S sətirindən keçin və istifadə edin openTag etiketi açmaq və ya bağlamaq lazım olduğunu yoxlamaq üçün.
4. Sonda etiket hələ də açıqdırsa, onu bağlamalıyıq.

String LeetCode Həllində qalın sözlər üçün kod

Java Proqramı

class Solution {
    public String boldWords(String[] words, String s) {
        boolean[] bold = new boolean[s.length() + 1];
        for(String w : words)
            for(int i = s.indexOf(w); i != -1; i = s.indexOf(w, i + 1))
                Arrays.fill(bold, i, i + w.length(), true);
        StringBuilder r = new StringBuilder(bold[0] ? "<b>" : "");
        for(int i = 0; i < bold.length - 1; i++){
            r.append(s.charAt(i));
            r.append(bold[i] && !bold[i + 1] ? "</b>" : "");
            r.append(!bold[i] && bold[i + 1] ? "<b>" : "");
        }
        return r.toString();
    }
}

C ++ Proqramı

class Solution {
public:
    string boldWords(vector<string>& words, string S) {
        vector<bool> bold(S.size(), false);
        for(int i=0;i<words.size();i++) {
            for(int j=0;j+words[i].size()<=S.size();j++) {
                if(S.substr(j, words[i].size())!=words[i]) continue;
                for(int k=0;k<words[i].size();k++) bold[j+k]=true;
            }
        }
        string res;
        if(bold[0]) res+="<b>";
        for(int i=0;i<S.size();i++) {
            res.append(1, S[i]);
            if(i==S.size()-1) break;
            if(!bold[i]&&bold[i+1]) res+="<b>";
            else if(bold[i]&&!bold[i+1]) res+="</b>";
        }
        if(bold.back()) res+="</b>";
        return res;
    }
};

String LeetCode Həllində Qalın Sözlər üçün Mürəkkəblik Təhlili

Qoy N giriş sətirinin uzunluğu olsun.

Zamanın mürəkkəbliyi: O (N)

Biz yalnız giriş sətri üzərində təkrar edirik. Beləliklə, O(N) vaxtını alacaq.

Kosmik mürəkkəblik: O (N)

Biz sətri massivdə saxlayırıq. Beləliklə, O(N) yerini tutacaq.

Referans: https://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style/Text_formatting