{"id":11747,"date":"2024-08-06T21:22:36","date_gmt":"2024-08-06T21:22:36","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11747"},"modified":"2024-08-06T21:23:09","modified_gmt":"2024-08-06T21:23:09","slug":"programming-problem-number-of-pairs-of-strings-with-concatenation-equal-to-target","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11747","title":{"rendered":"[Programming Problem] Number of Pairs of Strings With Concatenation Equal to Target"},"content":{"rendered":"<p>[<a href=\"https:\/\/leetcode.com\/problems\/number-of-pairs-of-strings-with-concatenation-equal-to-target\/\" rel=\"noopener\" target=\"_blank\">Problem Link<\/a>]<\/p>\n<pre lang=\"text\">\r\nGiven an array of digit strings nums and a digit string target, return the number of pairs of indices (i, j) (where i != j) such that the concatenation of nums[i] + nums[j] equals target.\r\n\r\nExample 1:\r\n\r\nInput: nums = [\"777\",\"7\",\"77\",\"77\"], target = \"7777\"\r\nOutput: 4\r\nExplanation: Valid pairs are:\r\n- (0, 1): \"777\" + \"7\"\r\n- (1, 0): \"7\" + \"777\"\r\n- (2, 3): \"77\" + \"77\"\r\n- (3, 2): \"77\" + \"77\"\r\nExample 2:\r\n\r\nInput: nums = [\"123\",\"4\",\"12\",\"34\"], target = \"1234\"\r\nOutput: 2\r\nExplanation: Valid pairs are:\r\n- (0, 1): \"123\" + \"4\"\r\n- (2, 3): \"12\" + \"34\"\r\nExample 3:\r\n\r\nInput: nums = [\"1\",\"1\",\"1\"], target = \"11\"\r\nOutput: 6\r\nExplanation: Valid pairs are:\r\n- (0, 1): \"1\" + \"1\"\r\n- (1, 0): \"1\" + \"1\"\r\n- (0, 2): \"1\" + \"1\"\r\n- (2, 0): \"1\" + \"1\"\r\n- (1, 2): \"1\" + \"1\"\r\n- (2, 1): \"1\" + \"1\"\r\n<\/pre>\n<p>My initial thought was to use some sort of advanced pattern searching algorithm like <a href=\"https:\/\/www.geeksforgeeks.org\/rabin-karp-algorithm-for-pattern-searching\/\" rel=\"noopener\" target=\"_blank\">Robin Karp<\/a>. But there was a more straightforward way simply using hashtables (involing suffixes and prefixes).<\/p>\n<p>&#8211; Add all suffixes and prefixes of target into a set<br \/>\n&#8211; Loop through nums and check if both suffix and prefix are part of the set.<br \/>\n&#8211; <strong>Gotcha<\/strong>: In the example, target=&#8217;7777&#8242; nums: [&#8216;7777&#8217;, &#8216;777&#8217;], (0, 1) would show up as a pair which its clearly not.<br \/>\n&#8211; Add another condition to make sure length of nums[i] + nums[j] equals length of target.<br \/>\n&#8211; <strong>Another gotcha<\/strong> was how we build suffixes (look at comment below).<\/p>\n<pre lang=\"javascript\">\r\n\/**\r\n * @param {string[]} nums\r\n * @param {string} target\r\n * @return {number}\r\n *\/\r\nvar numOfPairs = function(nums, target) {\r\n    const prefixes = new Set();\r\n    const suffixes = new Set();\r\n\r\n    let curr = '';\r\n    for ( let i = 0 ; i < target.length ; i++ ) {\r\n        curr += target[i];\r\n        prefixes.add(curr);\r\n    }\r\n\r\n    curr = '';\r\n    for ( let i = target.length-1 ; i >= 0 ; i-- ) {\r\n        \/\/ curr += target[i] will fail.\r\n        \/\/ If you do that, you'll be comparing suffixes in reverse order.\r\n        curr = target[i] + curr; \r\n        suffixes.add(curr);\r\n    }\r\n\r\n    let cnt = 0;\r\n    for ( let i = 0 ; i < nums.length ; i++ ) {\r\n        for ( let j = 0 ; j < nums.length ; j++ ) {\r\n            if ( i === j ) continue;\r\n            if ( \r\n                prefixes.has(nums[i]) &#038;&#038;\r\n                suffixes.has(nums[j]) &#038;&#038;\r\n                (nums[i].length + nums[j].length) === target.length  ) {\r\n                    cnt++\r\n                }            \r\n        }\r\n    }\r\n\r\n    return cnt;\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>[Problem Link] Given an array of digit strings nums and a digit string target, return the number of pairs of indices (i, j) (where i != j) such that the concatenation of nums[i] + nums[j] equals target. Example 1: Input: nums = [&#8220;777&#8243;,&#8221;7&#8243;,&#8221;77&#8243;,&#8221;77&#8221;], target = &#8220;7777&#8221; Output: 4 Explanation: Valid pairs are: &#8211; (0, 1): [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11747","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11747","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11747"}],"version-history":[{"count":3,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11747\/revisions"}],"predecessor-version":[{"id":11749,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11747\/revisions\/11749"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11747"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11747"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11747"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}