{"id":4803,"date":"2021-12-13T15:48:08","date_gmt":"2021-12-13T10:18:08","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4803"},"modified":"2021-12-13T15:48:09","modified_gmt":"2021-12-13T10:18:09","slug":"letter-combinations-of-a-phone-number","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/letter-combinations-of-a-phone-number\/","title":{"rendered":"Letter Combinations of a Phone Number"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-backtracking\">Approach: Backtracking<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a digit string, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5014 pk-lazyload\"  width=\"284\"  height=\"343\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 284px) 100vw, 284px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-3.png 644w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-3-248x300.png 248w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-3-380x459.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-3-550x664.png 550w\" ><\/figure><\/div>\n\n\n\n<p><strong>The digit 0 maps to 0 itself.<\/strong><br><strong>The digit 1 maps to 1 itself.<\/strong><\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input: Digit = &#8220;23&#8221;<\/strong><br><strong>Output: [&#8220;ad&#8221;, &#8220;ae&#8221;, &#8220;af&#8221;, &#8220;bd&#8221;, &#8220;be&#8221;, &#8220;bf&#8221;, &#8220;cd&#8221;, &#8220;ce&#8221;, &#8220;cf&#8221;].<\/strong><br><strong>Explanation: &nbsp; <\/strong>The list shows the different possible combinations of the strings possible.<\/p>\n\n\n\n<ul><li>\u201cad\u201d &#8211; Press digit 2 once, digit 3 once.<\/li><li>\u201cae\u201d- &nbsp; Press digit 2 once, digit 3 twice<\/li><li>\u201caf\u201d &#8211;&nbsp; Press digit 2 twice, digit 3 once, and so on.<\/li><\/ul>\n\n\n\n<p><strong>Input: &nbsp; Digit = &#8220;2&#8221;<\/strong><br><strong>Output: [&#8220;a&#8221;, \u201cb\u201d, \u201cc\u201d]<\/strong><\/p>\n\n\n\n<h2 id=\"approach-backtracking\">Approach: Backtracking<\/h2>\n\n\n\n<p>The problem can be solved using the backtracking approach. The idea is to consider a digit as the <strong>starting point <\/strong>and generate all possible combinations with that letter. Check the below illustration for a better understanding.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1200\"  height=\"750\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5015 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Algorithm.gif\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>If the input is empty, simply return an empty array.<\/li><li>Initialize a hashmap that maps digits to their letters, i.e. mapping &#8220;2&#8221; to &#8220;a&#8221;, &#8220;b&#8221;, and &#8220;c&#8221;.<\/li><li>Consider a backtracking function for generating all possible combinations:<ul><li>Consider the parameters of the backtracking function as the <strong>path<\/strong>, i.e the current path we are traversing on and the <strong>index<\/strong>, i.e. on the digit we are on.<\/li><li>The base case would be, if our current combination of letters is the same length as the input digits, that iteration is complete. Therefore, insert it into the answer list, and backtrack.<\/li><li>Else, find all the possible combinations of letters that correspond with the current digit i.e. <strong>digits[index]<\/strong>.<\/li><li>Traverse through the letters. For each letter, insert the letter to our current <strong>path<\/strong>, and <strong>backtrack<\/strong> again, and increment the <strong>index <\/strong>by 1.<\/li><li>Remove the letter from the path once the iteration is completed.<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution {\n  public:\n    vector &lt; string > letterCombinations(string digits) {\n      if (!digits.size()) {\n        return {};\n      }\n \n      vector &lt; string > combs;\n      const vector &lt; string > chars = {\n        \"0\",\n        \"1\",\n        \"abc\",\n        \"def\",\n        \"ghi\",\n        \"jkl\",\n        \"mno\",\n        \"pqrs\",\n        \"tuv\",\n        \"wxyz\"\n      };\n      string builder;\n      build(builder, 0, digits, chars, combs);\n      return combs;\n    }\n  void build(string builder, int i,\n    const string &amp; digits,\n      const vector &lt; string > &amp; chars, vector &lt; string > &amp; combs) {\n    if (i == digits.size()) {\n      combs.push_back(builder);\n      return;\n    }\n \n    int d = digits[i] - '0';\n    for (char ch: chars[d]) {\n      build(builder + ch, i + 1, digits, chars, combs);\n    }\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution {\n  private List &lt; String > combinations = new ArrayList &lt; > ();\n  private Map &lt; Character, String > letters = Map.of(\n    '2', \"abc\", '3', \"def\", '4', \"ghi\", '5', \"jkl\",\n    '6', \"mno\", '7', \"pqrs\", '8', \"tuv\", '9', \"wxyz\");\n  private String phoneDigits;\n \n  public List &lt; String > letterCombinations(String digits) {\n    if (digits.length() == 0) {\n      return combinations;\n    }\n    phoneDigits = digits;\n    backtrack(0, new StringBuilder());\n    return combinations;\n  }\n \n  private void backtrack(int index, StringBuilder path) {\n    if (path.length() == phoneDigits.length()) {\n      combinations.add(path.toString());\n      return;\n    }\n    String possibleLetters = letters.get(phoneDigits.charAt(index));\n    for (char letter: possibleLetters.toCharArray()) {\n      path.append(letter);\n      backtrack(index + 1, path);\n      path.deleteCharAt(path.length() - 1);\n    }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Solution:\n    def letterCombinations(self, digits: str) -> List[str]:\n        if len(digits) == 0:\n            return []\n \n        letters = {\n            \"2\": \"abc\",\n            \"3\": \"def\",\n            \"4\": \"ghi\",\n            \"5\": \"jkl\",\n            \"6\": \"mno\",\n            \"7\": \"pqrs\",\n            \"8\": \"tuv\",\n            \"9\": \"wxyz\",\n        }\n \n        def backtrack(index, path):\n            if len(path) == len(digits):\n                combinations.append(\"\".join(path))\n                return\n \n            possible_letters = letters[digits[index]]\n            for letter in possible_letters:\n \n                path.append(letter)\n \n                backtrack(index + 1, path)\n \n                path.pop()\n \n        combinations = []\n        backtrack(0, [])\n        return combinations<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(4^N * N), where N is the length of a digit string<br><strong>Space Complexity:<\/strong> O(N)<\/p>\n\n\n\n<p><strong>Practice Problem<\/strong> &#8211; <a href=\"https:\/\/www.interviewbit.com\/problems\/letter-phone\/\" target=\"_blank\" rel=\"noreferrer noopener\">Letter Phone<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. How does the backtracking function work?<\/strong><br>A. The backtracking approach is to consider a digit as the <strong>starting point<\/strong> and generate all possible combinations with that letter. The base case would be, if our current combination of letters is the same length as the input <strong>digits<\/strong>, that iteration is complete. Therefore, insert it into the answer list, and backtrack. Else, find all the possible combinations of letters that correspond with the current digit i.e. <strong>digits[index]<\/strong>.<\/p>\n\n\n\n<p><strong>Q. What is the time complexity and space complexity of the backtracking approach?<\/strong><br>A. The time complexity of the backtracking approach is O(4^N * N) and space complexity is O(N).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a digit string, return all possible letter combinations that the number could represent. A mapping&hellip;\n","protected":false},"author":5,"featured_media":5013,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[672],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4803"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4803"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4803\/revisions"}],"predecessor-version":[{"id":5016,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4803\/revisions\/5016"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5013"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4803"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4803"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4803"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}