标签： 字符串

目标

给你一个字符串 s，它由小写英文字母和特殊字符：*、# 和 % 组成。

请根据以下规则从左到右处理 s 中的字符，构造一个新的字符串 result：

• 如果字符是 小写 英文字母，则将其添加到 result 中。
• 字符 '*' 会 删除 result 中的最后一个字符（如果存在）。
• 字符 '#' 会 复制 当前的 result 并 追加 到其自身后面。
• 字符 '%' 会 反转 当前的 result。

在处理完 s 中的所有字符后，返回最终的字符串 result。

示例 1：

输入： s = "a#b%*"
输出： "ba"
解释：
i s[i] 操作 当前 result
0 'a' 添加 'a' "a"
1 '#' 复制 result "aa"
2 'b' 添加 'b' "aab"
3 '%' 反转 result "baa"
4 '*' 删除最后一个字符 "ba"
因此，最终的 result 是 "ba"。

示例 2：

输入： s = "z*#"
输出： ""
解释：
i s[i] 操作 当前 result
0 'z' 添加 'z' "z"
1 '*' 删除最后一个字符 ""
2 '#' 复制字符串 ""
因此，最终的 result 是 ""。

说明:

• 1 <= s.length <= 20
• s 只包含小写英文字母和特殊字符 *、# 和 %。

思路

根据规则从左到右处理字符串 s，如果时小写字母添加到结果 result，如果是 * 删除 result 的最后一个字符，如果是 # 将 result 追加到自身的后面，如果是 % 则反转当前的 result。

字符串长度最大为 20，可以暴力模拟。

代码

/**
 * @date 2025-07-14 9:15
 */
public class ProcessStrQ1 {

    public String processStr(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '*':
                    if (sb.length() > 0) {
                        sb.deleteCharAt(sb.length() - 1);
                    }
                    break;
                case '#':
                    sb.append(sb);
                    break;
                case '%':
                    sb.reverse();
                    break;
                default:
                    sb.append(c);
            }
        }
        return sb.toString();
    }

}

性能

目标

给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且 每个 小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。

返回 word 中 特殊字母 的数量。

示例 1:

输入：word = "aaAbcBC"
输出：3
解释：
特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = "abc"
输出：0
解释：
word 中不存在特殊字母。

示例 3:

输入：word = "AbBCab"
输出：0
解释：
word 中不存在特殊字母。

说明：

• 1 <= word.length <= 2 * 10^5
• word 仅由小写和大写英文字母组成。

思路

有一个字符串 word，返回其中大小写同时存在，且 所有小写都在其大写之前出现 的的字母个数。

与 3120_统计特殊字母的数量I 相比，本题多了顺序条件。

使用两个数组标记字母（无论大小写，统一用 0 ~ 25 表示）是否被计数以及是否被删除：

• 如果当前字母是大写：
  • 之前大小写都已出现（计数 或者 删除都已经处理过了），直接跳过
  • 对应的小写已经出现，计数（上面的条件保证了不会重复计数），并标记为已计数
• 如果当前字母是小写：
  • 之前大小写都已出现，且已计数（不一定被计数，因为小写可能后出现）未被标记为已删除，则计数减一，并标记为已删除
  • 注意如果之前只出现过大写，不用处理，因为没有被计数

代码

/**
 * @date 2026-05-26 9:06
 */
public class NumberOfSpecialChars3121 {

    /**
     * A(65):  1000001
     * Z(90):  1011010
     * a(97):  1100001
     * z(122): 1111010
     * 31: 0011111
     * 32: 0100000
     */
    public int numberOfSpecialChars_v1(String word) {
        Set<Integer> set = new HashSet<>();
        int n = word.length();
        boolean[] rm = new boolean[26];
        boolean[] add = new boolean[26];
        int res = 0;
        for (int i = 0; i < n; i++) {
            int c = word.charAt(i);
            // 将字母映射到 0 ~ 25，不区分大小写
            int index = (c & 31) - 1;
            // flag 为 0 表示大写字母，为 1 是小写字母
            int flag = c & 32;
            // 如果之前已经遇到过字母的大小写
            if (set.contains(c) && set.contains(c ^ (1 << 5))) {
                // 如果当前是大写，无需处理，因为需要加的话前面已经加了，需要减的前面已经减了
                if (flag == 0){
                    continue;
                }
                // 如果当前是小写，计数过且没减过，计数减一，并标记
                // 注意，如果之前只遇到过大写，不用处理，因为不满足条件没有被计数
                if (!rm[index] && add[index]){
                    rm[index] = true;
                    res--;
                }
            }
            // 如果当前是大写并且之前出现过小写，标记并计数
            if (flag == 0 && set.contains(c + 32)){
                add[index] = true;
                res++;
            }
            set.add(c);
        }
        return res;
    }

}

性能

目标

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

说明：

• 1 <= arr1.length, arr2.length <= 5 * 10^4
• 1 <= arr1[i], arr2[i] <= 10^8

思路

有两个数组 arr1 和 arr2，返回所有数对 (arr1[i], arr2[j]) 中最长公共前缀的长度。

将 arr1 中每个数字的前缀都计入哈希表，同时判断 arr2 中每个元素的的前缀是否在哈希表中，取前缀的最大长度即可。

或者可以将 arr1 的每个元素都加入 字典树，枚举 arr2 的每一个元素，计算其在字典树中公共前缀的最大长度。

代码

/**
 * @date 2026-05-21 9:03
 */
public class LongestCommonPrefix3043 {

    static class Trie {
        public Trie[] children = new Trie[10];

        public void insert(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    cur.children[d] = new Trie();
                }
                cur = cur.children[d];
            }
        }

        public int prefixLength(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            int l = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    break;
                }
                cur = cur.children[d];
                l++;
            }
            return l;
        }
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie root = new Trie();
        for (int num : arr1) {
            root.insert(num);
        }
        int res = 0;
        for (int num : arr2) {
            res = Math.max(res, root.prefixLength(num));
        }
        return res;
    }

}

性能

目标

给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。

示例 1：

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。
所以我们返回 ["word","note","wood"] 。

示例 2：

输入：queries = ["yes"], dictionary = ["not"]
输出：[]
解释：
"yes" 需要超过 2 次编辑才能得到 "not" 。
所以我们返回空数组。

说明：

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• 所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

思路

有两个字符串数组 queries 和 dictionary，它们的字符串长度都相等，每次编辑可以将 queries 中的任意字符串的任意一个字母改成其它字母，按 queries 顺序返回最多两次编辑能够与 dictionary 中某个字符串相同的 queries[i]。

暴力枚举，比较 queries[i] 与 dictionary 中的每个字符串不同的字符个数，如果小于等于 2 加入结果集合。

代码

/**
 * @date 2026-04-22 9:04
 */
public class TwoEditWords2452 {

    public List<String> twoEditWords_v2(String[] queries, String[] dictionary) {
        List<String> res = new ArrayList<>();
        for (String query : queries) {
            if (check(query, dictionary)) {
                res.add(query);
            }
        }
        return res;
    }

    public boolean check(String query, String[] dictionary) {
        for (String dict : dictionary) {
            int dis = 0;
            for (int k = 0; k < dict.length() && dis <= 2; k++) {
                if (query.charAt(k) != dict.charAt(k)) {
                    dis++;
                }
            }
            if (dis <= 2) {
                return true;
            }
        }
        return false;
    }

}

性能