Posted on Feb 16, 2021
Solution: Letter Case Permutation
This is part of a series of Leetcode solution explanations ( index ). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums .
Leetcode Problem #784 ( Medium ): Letter Case Permutation
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. You can return the output **in any order .
- S will be a string with length between 1 and 12 .
- S will consist only of letters or digits.
When a problem asks us to deal with permutations, one of the obvious approaches is via recursion as recursion will allow us to fire off our helper function down each branching possibility.
Recursion also naturally favors a DFS approach, which is also good because it ensures that our recursion stack never gets too deep.
Our recursive helper function ( dfs ) is actually quite simple. If we start with the input string ( S ) fully lowercased, then we just need to make sure that each version of dfs calls itself down two branches: one in which the current character is left unchanged, and a second in which the character has been uppercased, but only if the character is a letter.
Then, whenever we reach the end of S , we can add the permutation to our answer array ( ans ).
Java deals with char arrays faster than it does strings, so we can pass a reference to a singular central char array ( chArr ) and modify it as we go. This also means that we have to remember to undo our toUpperCase after the second dfs is fired off so that later recursions reaching this character start with it in lower case.
C++ alone out of the four languages has mutable strings, so we can just pass a full copy of S down and modify each char individually, rather than having to build out a res .
Top comments (1)
Templates let you quickly answer FAQs or store snippets for re-use.
- Email [email protected]
- Location Kolkata, India
- Joined Jul 3, 2020
Here's another solution. We can also use a Bit-Masking approach to solve this problem.
Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink .
Hide child comments as well
For further actions, you may consider blocking this person and/or reporting abuse
Mr. G - Nov 9
🙌 7 Tips to Build Your GitHub Profile Like a PRO 🚀
Bap - Nov 16
Suraj Vishwakarma - Nov 30
Python Memory Management Best Practices
TelemetryHub - Nov 8
Once suspended, seanpgallivan will not be able to comment or publish posts until their suspension is removed.
Once unsuspended, seanpgallivan will be able to comment and publish posts again.
Once unpublished, all posts by seanpgallivan will become hidden and only accessible to themselves.
If seanpgallivan is not suspended, they can still re-publish their posts from their dashboard.
Once unpublished, this post will become invisible to the public and only accessible to seanpgallivan.
They can still re-publish the post if they are not suspended.
Thanks for keeping DEV Community safe. Here is what you can do to flag seanpgallivan:
seanpgallivan consistently posts content that violates DEV Community's code of conduct because it is harassing, offensive or spammy.
Unflagging seanpgallivan will restore default visibility to their posts.
We're a place where coders share, stay up-to-date and grow their careers.
784. Letter Case Permutation
- Time: $O(2^n)$
- Space: $O(2^n)$
Detect squares, minimum interval to include each query, merge triplets to form target triplet, hand of straights, distinct subsequences, min cost climbing stairs, swim in rising water, network delay time, min cost to connect all points, redundant connection, walls and gates, k closest points to origin, kth largest element in a stream, count good nodes in binary tree, binary tree right side view, number of connected components in an undirected graph, non overlapping intervals, lowest common ancestor of a binary search tree, graph valid tree, find minimum in rotated sorted array, encode and decode strings, house robber ii, subtree of another tree, counting bits, reverse bits, meeting rooms, word ladder ii, wiggle sort ii, valid phone numbers, letter case permutation.
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.
Input: S = “r2q” Output: [“r2q”, “R2q”, “r2Q”, “R2Q”]. Input: S = “678” Output: [“678”]
- S will be a string with length between 1 and 12.
- S will consist only of letters or digits.
We don’t have to take care of digits as they can’t help to find more pernutations. We only have letters with us now. Suppose a string have L letters in it. The number of possible permutation will 2 L .
This can be represented by bitmask bits.
For Example: we have g5h, we can represent all the possible permutations as g5h = 00, g5H = 01, G7h = 10, G7H = 11. Digits given in the input string are not included in bitmask.
According the possible bitmask, find out all the permutations, taking one bitmask at a time.
- Time Complexity: O(2 n *n).
- Space Complexity: O(2 n *n).
Terms & Conditions
Data Structures & Algorithms
Company Wise Interview Questions
Blind 75 Practice Problems With Solutions
Divide & Conquer
Modified Binary Search
Google Interview Questions
Amazon Interview Questions
Adobe Interview Questions
Microsoft Interview Questions
Oracle Interview Questions
Uber Interview Questions
LinkedIn Interview Questions
Flipkart Interview Questions
Facebook Interview Questions
Goldman Sachs Interview Questions
Huawei Interview Questions