{"id":764,"date":"2025-07-22T14:49:00","date_gmt":"2025-07-22T09:19:00","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=764"},"modified":"2025-07-22T14:52:02","modified_gmt":"2025-07-22T09:22:02","slug":"letter-combinations-of-a-phone-number","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/","title":{"rendered":"Letter Combinations of a Phone Number | Leetcode 17 | Optimal Solution in Python"},"content":{"rendered":"\n<p>Given a string containing digits from&nbsp;<code>2-9<\/code>&nbsp;inclusive, return all possible letter combinations that the number could represent. Return the answer in&nbsp;<strong>any order<\/strong>.<\/p>\n\n\n\n<p>A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/letter-combinations-of-a-phone-number\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<figure class=\"wp-block-image is-resized\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/03\/15\/1200px-telephone-keypad2svg.png\" alt=\"\" style=\"width:331px;height:auto\"\/><\/figure>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> digits = \"23\"<br><strong>Output:<\/strong> [\"ad\",\"ae\",\"af\",\"bd\",\"be\",\"bf\",\"cd\",\"ce\",\"cf\"]<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> digits = \"\"<br><strong>Output:<\/strong> []<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> digits = \"2\"<br><strong>Output:<\/strong> [\"a\",\"b\",\"c\"]<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>0 &lt;= digits.length &lt;= 4<\/code><\/li>\n\n\n\n<li><code>digits[i]<\/code>\u00a0is a digit in the range\u00a0<code>['2', '9']<\/code>.<\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-7b444306-0c0b-4ab2-987e-231fa6108485\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#0-solution-backtracking-approach\" style=\"\">Solution: Backtracking Approach<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/letter-combinations-of-a-phone-number\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-backtracking-approach\">Solution: Backtracking Approach<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like dialing a phone number where each digit has multiple letter options, and you want to try every possible word you could spell! Imagine you have an old phone keypad where pressing &#8220;2&#8221; could give you &#8216;a&#8217;, &#8216;b&#8217;, or &#8216;c&#8217;, and pressing &#8220;3&#8221; could give you &#8216;d&#8217;, &#8216;e&#8217;, or &#8216;f&#8217;. If you press &#8220;23&#8221;, you want to know all possible 2-letter combinations you could spell.<\/p>\n\n\n\n<p>The key insight is that this is a&nbsp;<strong>tree exploration problem<\/strong>. For each digit position, we have multiple choices (letters), and we need to explore all possible paths through this tree. It&#8217;s like having a decision tree where at each level (digit position), you branch out to try all possible letters for that digit.<\/p>\n\n\n\n<p>For example, with &#8220;23&#8221;:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"      Root\n    \/   |   \\\n   a    b    c    (choices for digit '2')\n  \/|\\  \/|\\  \/|\\\n d e f d e f d e f (choices for digit '3')\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">      Root<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    \/   |   \\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">   a    b    <\/span><span style=\"color: #DCDCAA\">c<\/span><span style=\"color: #D4D4D4\">    (choices <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> digit <\/span><span style=\"color: #CE9178\">&#39;2&#39;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">  \/|\\  \/|\\  \/|\\<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\"> d e f d e f d e <\/span><span style=\"color: #DCDCAA\">f<\/span><span style=\"color: #D4D4D4\"> (choices <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> digit <\/span><span style=\"color: #CE9178\">&#39;3&#39;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Each path from root to leaf gives us one valid combination.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Setup Digit-to-Letter Mapping<\/strong>: Create a dictionary that maps each digit to its corresponding letters, just like a phone keypad.<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When we&#8217;ve processed all digits (index == len(digits)), we&#8217;ve formed a complete combination, so add it to our result.<\/li>\n\n\n\n<li><strong>Recursive Choice<\/strong>: For the current digit at\u00a0<code>index<\/code>, get all possible letters it can represent. For each letter, make a recursive call to process the next digit, building the current string as we go.<\/li>\n\n\n\n<li><strong>String Building<\/strong>: Instead of maintaining a list and popping (like in subset problems), we build the string by concatenation since strings are immutable in Python &#8211; this naturally handles the &#8220;backtracking&#8221; for us.<\/li>\n\n\n\n<li><strong>Edge Case<\/strong>: Handle empty input by returning empty list immediately.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def __init__(self):\n        # Phone keypad mapping - same as traditional phone buttons\n        self.digits_to_letters = {\n            &quot;2&quot;: &quot;abc&quot;,\n            &quot;3&quot;: &quot;def&quot;, \n            &quot;4&quot;: &quot;ghi&quot;,\n            &quot;5&quot;: &quot;jkl&quot;,\n            &quot;6&quot;: &quot;mno&quot;,\n            &quot;7&quot;: &quot;pqrs&quot;,\n            &quot;8&quot;: &quot;tuv&quot;,\n            &quot;9&quot;: &quot;wxyz&quot;,\n        }\n\n    def helper(self, digits, ans, index, current):\n        # Base case: processed all digits, we have a complete combination\n        if index == len(digits):\n            ans.append(current)  # Add the complete combination to results\n            return\n\n        # Get all possible letters for the current digit\n        letters = self.digits_to_letters.get(digits[index], &quot;&quot;)\n        \n        # Try each possible letter for this digit position\n        for letter in letters:\n            # Recursive call: move to next digit, extend current combination\n            self.helper(digits, ans, index + 1, current + letter)\n\n    def letterCombinations(self, digits):\n        ans = []\n        # Handle edge case: empty input\n        if not digits:\n            return ans\n        \n        # Start the backtracking process\n        self.helper(digits, ans, 0, &quot;&quot;)  # index=0, current=&quot;&quot;\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Phone keypad mapping - same as traditional phone buttons<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.digits_to_letters = {<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;2&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;abc&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;3&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;def&quot;<\/span><span style=\"color: #D4D4D4\">, <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;4&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;ghi&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;5&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;jkl&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;6&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;mno&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;7&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;pqrs&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;8&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;tuv&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #CE9178\">&quot;9&quot;<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #CE9178\">&quot;wxyz&quot;<\/span><span style=\"color: #D4D4D4\">,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        }<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">helper<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">digits<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">current<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: processed all digits, we have a complete combination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index == <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(digits):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(current)  <\/span><span style=\"color: #6A9955\"># Add the complete combination to results<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Get all possible letters for the current digit<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        letters = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.digits_to_letters.get(digits[index], <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try each possible letter for this digit position<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> letter <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> letters:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Recursive call: move to next digit, extend current combination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.helper(digits, ans, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, current + letter)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">letterCombinations<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">digits<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Handle edge case: empty input<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> digits:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Start the backtracking process<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.helper(digits, ans, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #CE9178\">&quot;&quot;<\/span><span style=\"color: #D4D4D4\">)  <\/span><span style=\"color: #6A9955\"># index=0, current=&quot;&quot;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>The solution uses&nbsp;<strong>backtracking with string concatenation<\/strong>. The&nbsp;<code>digits_to_letters<\/code>&nbsp;dictionary mimics a phone keypad mapping. The&nbsp;<code>helper<\/code>&nbsp;function is the core recursive backtracking function:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Parameters<\/strong>:\n<ul class=\"wp-block-list\">\n<li><code>digits<\/code>: input string of digits<\/li>\n\n\n\n<li><code>ans<\/code>: result list to collect all combinations<\/li>\n\n\n\n<li><code>index<\/code>: current position in digits string<\/li>\n\n\n\n<li><code>current<\/code>: current combination being built<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When\u00a0<code>index == len(digits)<\/code>, we&#8217;ve made choices for all digits, so\u00a0<code>current<\/code>\u00a0contains a complete valid combination.<\/li>\n\n\n\n<li><strong>Recursive Case<\/strong>: Get all letters for\u00a0<code>digits[index]<\/code>, and for each letter, recursively solve for the remaining digits with the updated combination string.<\/li>\n<\/ul>\n\n\n\n<p>The beauty of using string concatenation (<code>current + letter<\/code>) is that it naturally creates a new string for each recursive branch, eliminating the need for explicit backtracking (no need to &#8220;undo&#8221; changes like with lists).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>digits = \"23\"<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"helper(digits='23', index=0, current='')&lt;br\/>Generate all letter combinations\"]\n    \n    %% Level 0: index=0, digit='2', letters='abc'\n    Root --- A[\"Try 'a'&lt;br\/>current='a'&lt;br\/>index=1\"]\n    Root --- B[\"Try 'b'&lt;br\/>current='b'&lt;br\/>index=1\"]\n    Root --- C[\"Try 'c'&lt;br\/>current='c'&lt;br\/>index=1\"]\n    \n    %% Level 1 from 'a': index=1, digit='3', letters='def'\n    A --- A1[\"Try 'd'&lt;br\/>current='ad'&lt;br\/>index=2\"]\n    A --- A2[\"Try 'e'&lt;br\/>current='ae'&lt;br\/>index=2\"]\n    A --- A3[\"Try 'f'&lt;br\/>current='af'&lt;br\/>index=2\"]\n    \n    %% Level 1 from 'b': index=1, digit='3', letters='def'\n    B --- B1[\"Try 'd'&lt;br\/>current='bd'&lt;br\/>index=2\"]\n    B --- B2[\"Try 'e'&lt;br\/>current='be'&lt;br\/>index=2\"]\n    B --- B3[\"Try 'f'&lt;br\/>current='bf'&lt;br\/>index=2\"]\n    \n    %% Level 1 from 'c': index=1, digit='3', letters='def'\n    C --- C1[\"Try 'd'&lt;br\/>current='cd'&lt;br\/>index=2\"]\n    C --- C2[\"Try 'e'&lt;br\/>current='ce'&lt;br\/>index=2\"]\n    C --- C3[\"Try 'f'&lt;br\/>current='cf'&lt;br\/>index=2\"]\n    \n    %% Level 2: Base case - index == len(digits)\n    A1 --- Result1[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'ad' to result\"]\n    A2 --- Result2[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'ae' to result\"]\n    A3 --- Result3[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'af' to result\"]\n    \n    B1 --- Result4[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'bd' to result\"]\n    B2 --- Result5[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'be' to result\"]\n    B3 --- Result6[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'bf' to result\"]\n    \n    C1 --- Result7[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'cd' to result\"]\n    C2 --- Result8[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'ce' to result\"]\n    C3 --- Result9[\"index=2 == len(digits)&lt;br\/>\u2705 Add 'cf' to result\"]\n    \n    %% Final result\n    Result1 --- Final[\"Final Result:&lt;br\/>['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']\"]\n    Result2 --- Final\n    Result3 --- Final\n    Result4 --- Final\n    Result5 --- Final\n    Result6 --- Final\n    Result7 --- Final\n    Result8 --- Final\n    Result9 --- Final\n\n    %% Styling\n    style Result1 fill:#90EE90\n    style Result2 fill:#90EE90\n    style Result3 fill:#90EE90\n    style Result4 fill:#90EE90\n    style Result5 fill:#90EE90\n    style Result6 fill:#90EE90\n    style Result7 fill:#90EE90\n    style Result8 fill:#90EE90\n    style Result9 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqVlt1umzAUx1_F8lSxSk4HmK-gZVKSprvZVderlV7wYRIkPiKHTO2qXPYt9nR7khkbCKMmsFyg-Bz-_-OffYT9CsMiItCFW-rvd-Dh1ssB-90XRfnowR1J94R-jJJtUh4Wio4VBJI8Is8LFYHwSCnJy4WiXH8O6KcvX0lOqF8S4KcpSElZEgrCIguS3C-TIj948EmYi-fVFfhGfpIUqO7Zk1dihVgd4cCq-kGonGcFZrMZWLK5PdAXoPgKL91OpR4LP62t2ApXjTDoCYMR4boRhj1hKBf2GDUQ0yKr5tvAai0s7sJGJK5hl4JUawpHfdSoW1lvK9c6vdGRvo5c1OFGF_d1sVw3QBpMJ12JrRkkDQZIa90gaUAu6gZJg_8jDaeTrkUvDZKGA6S1bpA0JBd1g6ThNFLdBSv_QEBYPWYCFiwWjDCvvw3XdQ9pvOA9ORzTsqKsjXsv85p_fr-BZRSBqpFBWQDKRed21DtW-lQrIrXCHSs81SqWWdUN1MU0JhoGUsxVF9OcaiXFXHUxralWFzDXXUx7omEoxVx3MZ2pVlLMdRdzPtXqAiZr8zt2RqVNVnz4RQvzUjzLCom3RMbl_o9V8yLed4i3DOL7jPgWIb66iC8J4jSIT-TpfLqI5j4X6YaxPGzIw6Y8bMnDtjzsyMPzbrhds-_lS5rkWzE-sAFpFy1O0tT9MFc3m7n6Pq-P5PFI3hjJmyN5ayRvj-Sdkfx8MC8a6H32H4_qxiFe2Vgb627p5RCx21kSQbekR4JgRmjmV0P4Wgk9WO5IRjzosr_sqPF5h3v5icn2fv6jKLJGSYvjdgfd2E8PbHTcR-y2dpv47OqXtVF2MESErotjXkJX1yzMXaD7Cp-hO8MmvjENzVGxrauqgTULwRfoavaNqquarTm2ZVq2rZonBH_xytqNYWNTNw3TMRymwae_L0sl7Q\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(4^n \u00d7 n) where n is the length of digits\n<ul class=\"wp-block-list\">\n<li>4^n because in worst case each digit maps to 4 letters (like &#8216;7&#8217; and &#8216;9&#8217;)<\/li>\n\n\n\n<li>The \u00d7n factor comes from string concatenation operations<\/li>\n\n\n\n<li>Total combinations = product of lengths of all digit mappings<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(n) for recursion stack depth\n<ul class=\"wp-block-list\">\n<li>Plus O(4^n \u00d7 n) for storing all result combinations<\/li>\n\n\n\n<li>Each combination string has length n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h2>\n\n\n\n<p>This approach is like systematically trying every possible word you could spell on an old phone by pressing the number keys. You go digit by digit, and for each digit, you try every letter it could represent. You build up your word letter by letter, and when you&#8217;ve used all the digits, you write down the complete word you spelled. The recursion naturally explores all possible &#8220;spelling paths&#8221; through your sequence of digit presses.<\/p>\n\n\n\n<p>The key insight is recognizing this as a\u00a0<strong>Cartesian product problem<\/strong>, we want all combinations where we pick one letter from each digit&#8217;s letter set. Backtracking is the perfect tool for systematically generating such combinations!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a string containing digits from&nbsp;2-9&nbsp;inclusive, return all possible letter combinations that the number could represent. Return the answer in&nbsp;any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Here&#8217;s the [Problem Link] to begin with. Example 1: Input:<\/p>\n","protected":false},"author":1,"featured_media":765,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[32,19],"class_list":{"0":"post-764","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-advance-recursion","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/letter-combinations-of-a-phone-number-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/764","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=764"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/764\/revisions"}],"predecessor-version":[{"id":769,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/764\/revisions\/769"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/765"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}