{"id":232116,"date":"2023-01-20T18:50:00","date_gmt":"2023-01-20T15:50:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=232116"},"modified":"2023-02-05T12:53:26","modified_gmt":"2023-02-05T09:53:26","slug":"algoritmen-foer-att-goera-ord-fet-i-html","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/sv\/algoritmen-foer-att-goera-ord-fet-i-html\/","title":{"rendered":"Algoritmen f\u00f6r att g\u00f6ra ord fet i HTML"},"content":{"rendered":"<blockquote>\n<p>Givet en upps\u00e4ttning nyckelord ord och en str\u00e4ng S, g\u00f6r alla upptr\u00e4danden av alla nyckelord i fet stil. Alla bokst\u00e4ver mellan <strong>och<\/strong> taggar blir fetstilta.<\/p>\n<p>Den returnerade str\u00e4ngen b\u00f6r anv\u00e4nda minsta m\u00f6jliga antal taggar, och naturligtvis b\u00f6r taggarna bilda en giltig kombination.<\/p>\n<p>Till exempel, med tanke p\u00e5 att orden = [&quot;ab&quot;, &quot;bc&quot;] och S = &quot;aabcd&quot;, b\u00f6r vi returnera &quot;a <strong>abc<\/strong> d&quot;. Observera att om du returnerar &quot; <strong>a<em><\/em><\/strong> b<em><\/em>cd&quot; skulle fler taggar anv\u00e4ndas, s\u00e5 det \u00e4r felaktigt.<\/p>\n<p>Notera:<\/p>\n<ul>\n<li>ord har l\u00e4ngd i intervallet [0, 50].<\/li>\n<li>ord[i] har l\u00e4ngd i intervallet [1, 10].<\/li>\n<li>S har en l\u00e4ngd inom omr\u00e5det [0, 500].<\/li>\n<li>Alla tecken i ord[i] och S \u00e4r sm\u00e5 bokst\u00e4ver.<\/li>\n<\/ul>\n<\/blockquote>\n<h3>G\u00f6r str\u00e4ng fet med Bruteforce Algorithm<\/h3>\n<p>Utan kravet p\u00e5 det kortaste kan vi g\u00f6ra fetstil p\u00e5 varje f\u00f6rekomst av orden i listan. Eftersom vi f\u00e5r den ursprungliga <a href=\"https:\/\/wordpress.mediadoma.com\/sv\/hur-laegger-man-till-googles-soekmotor-i-wordpress-blogg-widget-enkel-html-kod\/\" title=\"HTML-str\u00e4ngen\">HTML-str\u00e4ngen<\/a> kan vi markera fetstil f\u00f6r varje tecken som visas i fetstilta ord.<\/p>\n<p>S\u00e5, med O(N)-mellanslag och O(NM) d\u00e4r N \u00e4r storleken p\u00e5 str\u00e4ngen och M \u00e4r den totala l\u00e4ngden p\u00e5 den fetstilta str\u00e4ngen, kommer f\u00f6ljande C++ <a href=\"https:\/\/helloacm.com\/algorithms-to-find-the-three-numbers-in-array-that-sum-up-to-zero-3sum\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">bruteforce-algoritm<\/a> att infoga minst HTML-taggar med fet stil som uppfyller kravet.<\/p>\n<pre><code>class Solution {\npublic:\n\u00a0 \u00a0 string boldWords(vector&lt;string&gt;&amp; words, string S) {\n\u00a0 \u00a0 \u00a0 \u00a0 int n = S.size();\n\u00a0 \u00a0 \u00a0 \u00a0 vector&lt;bool&gt; bold(n, false);\n\u00a0 \u00a0 \u00a0 \u00a0 for (const auto &amp;s: words) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 for (int i = 0; i + s.size() - 1 &lt; n; ++ i) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 bool ok = true;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 for (int k = 0; k &lt; s.size(); ++ k) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (s[k] != S[i + k]) { \/\/ bold string s not found in the string\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ok = false;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 break;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (ok) { \/\/ it is bold\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 for (int k = 0; k &lt; s.size(); ++ k) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 bold[i + k] = true; \/\/ mark the character bold\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 string ans = \"\";\n\u00a0 \u00a0 \u00a0 \u00a0 for (int i = 0; i &lt; n; ++ i) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\/ bold start boundary\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (bold[i] &amp;&amp; (i == 0 || !bold[i - 1])) ans += \"&lt;b&gt;\"; \n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ans += S[i];\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\/ bold end boundary\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (bold[i] &amp;&amp; (i == n - 1 || !bold[i + 1])) ans += \"&lt;\/b&gt;\";\n\u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 return ans;\n\u00a0 \u00a0 }\n};<\/code><\/pre>\n<p>Efter att de fetstilta tecknen \u00e4r markerade skannar vi str\u00e4ngen igen och letar efter gr\u00e4nserna och infogar taggarna d\u00e4refter.<\/p>\n<p><div id=\"PostUnique_PostSource\" style=\"padding-top: 50px\">Inspelningsk\u00e4lla:  <a target=\"_blank\" rel=\"noopener nofollow\" href=\"\/\/helloacm.com\" class=\"external external_icon\">helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Algoritmen f\u00f6r att g\u00f6ra ord fet i HTML<\/p>\n","protected":false},"author":1,"featured_media":224460,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_wp_rev_ctl_limit":""},"categories":[838,848,901,922,724],"tags":[1173],"class_list":["post-232116","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-guide-foer-nyboerjare","category-handledningar","category-koda","category-oevrig","category-utvecklaren","tag-affiai-sv"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts\/232116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/comments?post=232116"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts\/232116\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/media\/224460"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/media?parent=232116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/categories?post=232116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/tags?post=232116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}