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.
Example 1:
Input: S = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]
Example 2:
Input: S = "3z4"
Output: ["3z4","3Z4"]
Example 3:
Input: S = "12345"
Output: ["12345"]
Example 4:
Input: S = "0"
Output: ["0"]
Constraints:
S will be a string with length between 1 and 12.
S will consist only of letters or digits.
Solution:
Iterative:
class Solution {
Set<String> set = new HashSet<>();
Queue<String> queue = new LinkedList();
public List<String> letterCasePermutation(String s)
{
queue.add(s);
while(!queue.isEmpty())
{
String ss = queue.remove();
if(set.contains(ss)) continue;
set.add(ss);
for(int i=0;i<ss.length();i++)
{
char[] a = ss.toCharArray();
if(Character.isLetter(a[i]))
{
if(Character.isUpperCase(a[i])) a[i] = Character.toLowerCase(a[i]);
else a[i] = Character.toUpperCase(a[i]);
}
String temp = String.valueOf(a);
if(!set.contains(temp)) queue.add(temp);
}
}
return new ArrayList(set);
}
}
Recursive
class Solution {public List<String> letterCasePermutation(String S) {
List<String> result = new ArrayList<>();
char[] ch = S.toCharArray();
permute(ch, result, 0);
return result;
}
public void permute(char[] ch, List<String> result, int index) {
result.add(new String(ch));
for(int i=index; i< ch.length; i++) {
char c = ch[i];
if(Character.isLetter(c)) {
ch[i] = getOpposite(c);
permute(ch, result, i+1);
ch[i] = c;
}
}
}
public char getOpposite(char c){
return Character.isUpperCase(c) ? Character.toLowerCase(c) : Character.toUpperCase(c);
}
}
Commentaires