Daily LeetCode – day0093 0784. Letter Case Permutation

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 0784. Letter Case Permutation
class Solution {
    public List<String> letterCasePermutation(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        Queue<StringBuilder> queue = new LinkedList<>();
        queue.offer(new StringBuilder());
        for (char c : charArray) {
            char fill1;
            char fill2;
            int size = queue.size();
            if (c <= '9') {
                fill1 = c;
                for (int j = 0; j < size; ++j) {
                    queue.offer(queue.poll().append(fill1));
                }
            } else {
                if (c > 'Z') {
                    fill1 = c;
                    fill2 = (char) (c - 32);
                } else {
                    fill1 = (char) (c + 32);
                    fill2 = c;
                }
                for (int j = 0; j < size; ++j) {
                    StringBuilder sb1 = queue.poll();
                    StringBuilder sb2 = new StringBuilder(sb1.toString());
                    sb1.append(fill1);
                    queue.offer(sb1);
                    sb2.append(fill2);
                    queue.offer(sb2);
                }
            }
        }
        List<String> ans = new LinkedList<>();
        for (StringBuilder sb : queue) {
            ans.add(sb.toString());
        }
        return ans;
    }
}
学习笔记:
这是一道字符串大小写相关的题目,用到搜索算法。
就是数字不变,字母各种变。
本来打算写深度优先搜索,但是一想不对啊,这深度也太深了会崩溃的。
于是用了宽度优先搜索算法来完成。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注