Strings

Print All Possible Words from Phone Digits

Print all possible words from phone number digits. This question is asked by companies like microsoft, google, facebook, Amazon. Lets see example input/output to understand this problem. For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi Read More →

String Decode Problem

Problem: If a=1, b=2, c=3,….z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings. For example: Input: “1123″. You need to general all valid alphabet codes from this string. Output List aabc //a = 1, a = 1, b = 2, c = 3 Read More →

Word Ladder Problem

Problem: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary For example, Given: start = “hit” end = “cog” dict = ["hot","dot","dog","lot","log"] As one shortest Read More →

Edit Distance – DP Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Input: str1 = “cat”, str2 = “cut” Output: Read More →

Decode Ways Leetcode Java

Problem: A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ – 1 ‘B’ – 2 ‘Z’ – 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12″, it could be decoded as “AB” (1 2) or Read More →

Break String into Dictionary Words

Given an English dictionary (implemented as a hashmap (word -> meaning)) and a string without spaces, output all possible combinations of valid English words that when combined, reproduce the input string. e.g. input: “programmerit” output: {{pro, gram, merit}, {program, merit}, {programmer, it}} output: Solution: Recursive implementation: The idea is simple, we consider each prefix and Read More →

Check if Any Anagram of a String is Palindrome or Not

Examples: Input: str = “aaaad” Output: 1 // “aaaad” is a anagram of a palindrome “aadaa” Input: str = “abcd” Output: 0 // “abcd” is not a anagram of any palindrome. A Simple Solution is to take the input string, try every possible rotation of it and return true if a anagram is a palindrome. Read More →

Replace all spaces in a string with “%20″

Problem: Write a C program that will replace all spaces with ‘%20′ Solution: The algorithm is as follows: 1. Count the number of spaces during the first scan of the string. 2. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as Read More →

Group all Words in Set of Anagrams of Each Other in Dictionary

Problem: Given a dictionary with set of words in it. Write a program to group all words which are anagrams of each other in to sets. For example – Input: “bat”, “tar”, “xyz” , “tab”, “tar” Output:[["bat", tab"], ["tar", rat"],”xyz” ] Thi sproblem was asked in amazon interview. Steps: 1)Use some sort of a hash Read More →

Check if One String is a Rotation of Other String

Problem: Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ? If s1 = “crazyforcode” then the following are some of its rotated versions: “forcodecrazy” “codecrazyfor” Solution: Steps: First need to check if s1 and s2 are of the same length. Then check, if s2 is Read More →

Find Anagrams in array of Strings

Problem: You are given an array of strings and you have to print all the anagrams within the array. What is anagram – For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Solution: Let’s use this Read More →

Move the Spaces to Front of the String

Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place. string = “move these spaces to beginning” output =” movethesepacestobeginning” Solution: 1) Maintain two indices i and Read More →