{"id":9874,"date":"2022-10-31T09:18:48","date_gmt":"2022-10-31T16:18:48","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9874"},"modified":"2022-10-31T09:21:47","modified_gmt":"2022-10-31T16:21:47","slug":"leetcode-2451-odd-string-difference%ef%bf%bc","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-2451-odd-string-difference%ef%bf%bc\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2451.\u00a0Odd String Difference"},"content":{"rendered":"\n<p>You are given an array of equal-length strings&nbsp;<code>words<\/code>. Assume that the length of each string is&nbsp;<code>n<\/code>.<\/p>\n\n\n\n<p>Each string&nbsp;<code>words[i]<\/code>&nbsp;can be converted into a&nbsp;<strong>difference integer array<\/strong>&nbsp;<code>difference[i]<\/code>&nbsp;of length&nbsp;<code>n - 1<\/code>&nbsp;where&nbsp;<code>difference[i][j] = words[i][j+1] - words[i][j]<\/code>&nbsp;where&nbsp;<code>0 &lt;= j &lt;= n - 2<\/code>. Note that the difference between two letters is the difference between their&nbsp;<strong>positions<\/strong>&nbsp;in the alphabet i.e.&nbsp;the position of&nbsp;<code>'a'<\/code>&nbsp;is&nbsp;<code>0<\/code>,&nbsp;<code>'b'<\/code>&nbsp;is&nbsp;<code>1<\/code>, and&nbsp;<code>'z'<\/code>&nbsp;is&nbsp;<code>25<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, for the string&nbsp;<code>\"acb\"<\/code>, the difference integer array is&nbsp;<code>[2 - 0, 1 - 2] = [2, -1]<\/code>.<\/li><\/ul>\n\n\n\n<p>All the strings in words have the same difference integer array,&nbsp;<strong>except one<\/strong>. You should find that string.<\/p>\n\n\n\n<p>Return<em>&nbsp;the string in&nbsp;<\/em><code>words<\/code><em>&nbsp;that has different&nbsp;<strong>difference integer array<\/strong>.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"adc\",\"wzy\",\"abc\"]\n<strong>Output:<\/strong> \"abc\"\n<strong>Explanation:<\/strong> \n- The difference integer array of \"adc\" is [3 - 0, 2 - 3] = [3, -1].\n- The difference integer array of \"wzy\" is [25 - 22, 24 - 25]= [3, -1].\n- The difference integer array of \"abc\" is [1 - 0, 2 - 1] = [1, 1]. \nThe odd array out is [1, 1], so we return the corresponding string, \"abc\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"aaa\",\"bob\",\"ccc\",\"ddd\"]\n<strong>Output:<\/strong> \"bob\"\n<strong>Explanation:<\/strong> All the integer arrays are [0, 0] except for \"bob\", which corresponds to [13, -13].\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>3 &lt;= words.length &lt;= 100<\/code><\/li><li><code>n == words[i].length<\/code><\/li><li><code>2 &lt;= n &lt;= 20<\/code><\/li><li><code>words[i]<\/code>&nbsp;consists of lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Comparing with first string.<\/strong><\/h2>\n\n\n\n<p>Let us pick words[0] as a reference for comparison, assuming it&#8217;s valid. If we only found one instance say words[i], that is different than words[0], we know that words[i] is bad, otherwise we should see m &#8211; 1 different words which means words[0] itself is bad.<\/p>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string oddString(vector<string>& words) {\n    const int m = words.size();\n    const int n = words[0].size();\n    int count = 0;\n    int bad = 0;\n    for (int i = 1; i < m; ++i) \n      for (int j = 1; j < n; ++j) {\n        if (words[i][j] - words[i][j - 1] \n           != words[0][j] - words[0][j - 1]) {\n          ++count;\n          bad = i;\n          break;\n        }\n      }\n    return words[count == 1 ? bad : 0];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array of equal-length strings&nbsp;words. Assume that the length of each string is&nbsp;n. Each string&nbsp;words[i]&nbsp;can be converted into a&nbsp;difference integer array&nbsp;difference[i]&nbsp;of length&nbsp;n&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[20,442,222,4],"class_list":["post-9874","post","type-post","status-publish","format-standard","hentry","category-string","tag-array","tag-difference","tag-easy","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9874","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9874"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9874\/revisions"}],"predecessor-version":[{"id":9878,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9874\/revisions\/9878"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9874"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9874"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9874"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}