{"id":2215,"date":"2020-06-14T16:20:51","date_gmt":"2020-06-14T16:20:51","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2215"},"modified":"2022-03-30T23:08:33","modified_gmt":"2022-03-30T23:08:33","slug":"phone-number","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/phone-number\/","title":{"rendered":"Phone Number"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Backtracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a string containing numeric digits from 2<\/code> to 9<\/code> inclusive, return all possible letter combinations that the number could represent in lexicographical order.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to traverse the string and add each character which maps to the string numeric value recursively, removing characters after we have stored it to look for next combination.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Description :<\/h4>\n
\n

We need to explore all the possible combinations which can be solved with backtracking<\/strong>.
\nBacktracking<\/strong> is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem, moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.<\/p>\n

We will map the numeric values of the phone digits (2-9<\/code>) to the strings which it contains (see example). Now we will add each character which maps to the given numeric value and print the string when the length of our generated string reaches the length of the given string (why?). After printing the string we will remove the previous values (backtrack) and try other combinations which are left.<\/p>\n<\/blockquote>\n

Complexity Analysis :<\/h4>\n
\n

Space Complexity of this approach would be O(n)<\/code> since we are using an array.<\/p>\n<\/blockquote>\n

Solutions:<\/h3>\n\t\t\t\t\t\t