Java 第 14 课 383. 赎金信 748. 最短补全词

383. 赎金信691. 贴纸拼词748. 最短补全词基础知识

统计字母个数String method

Leetcode
知识点： 统计字母个数，字符串转字符数组，字母表影射到数组。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        c1 = collections.Counter(ransomNote)
        c2 = collections.Counter(magazine)
        x = c1 - c2
        # x 只保留值大于 0 的键，
        # x 只保留下了，magazine 不够的
        return len(x) == 0

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] cnt = new int[26]; // 字母和索引对应
        for (char c: magazine.toCharArray()) cnt[c - 'a']++;        
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) return false;
        }
        return true;
    }
}

Leetcode

from typing import List
from collections import Counter
from functools import lru_cache

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        @lru_cache(None)
        def dfs(target: str) -> int:
            if not target:
                return 0
            res = float('inf')
            for sticker in stickers:
                if target[0] not in sticker:
                    continue
                replacedWord = addSticker(sticker, target)
                res = min(res, dfs(replacedWord) + 1)
            return res

        # 耗尽Counter删除word里的字符
        def addSticker(sticker: Counter, word: str) -> str:
            for char in sticker:
                word = word.replace(char, '', sticker[char])
            return word

        stickers = [Counter(s) for s in stickers]
        res = dfs(target)
        return res if res != float('inf') else -1

Leetcode
知识点： 统计字符数，.length(), .charAt(), .isLetter(), .toLowerCase(), .isEmpty().

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())
        return min((word for word in words if not cnt - Counter(word)), key = len)

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] count = new int[26];
        for (int i = 0; i < licensePlate.length(); i++){
            char ch = licensePlate.charAt(i);
            if (Character.isLetter(ch)){
                ++count[Character.toLowerCase(ch) - 'a'];
            }
        }
        
        String res = "";
        for (String word: words){
            int[] cnt = new int[26];
            for (int j = 0; j < word.length(); j++){
                ++cnt[word.charAt(j) - 'a'];
            }   
            boolean ok = true;
            for (int k = 0; k < 26; k++){
                if (cnt[k] < count[k]){
                    ok = false;
                    break;
                }
            } 
            if (ok && (res.isEmpty() || word.length() < res.length())) res = word;       
        }
        return res;
    }
}

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] count = new int[26]; // 字母影射到数字
        // 遍历字符串，统计字母数。
        for (int i = 0; i < licensePlate.length(); i++){
            char ch = licensePlate.charAt(i);
            if (Character.isLetter(ch)){
                ++count[Character.toLowerCase(ch) - 'a'];
            }
        }
        
        String res = "";
        int minLen = Integer.MAX_VALUE;
        // 遍历字符串数组
        for (String word: words){
            int m = word.length();
            if (minLen <= m) continue; // 剪枝
            int[] cnt = new int[26];
            for (int j = 0; j < m; j++){
                ++cnt[word.charAt(j) - 'a'];
            }   
            boolean ok = true; // 用于符合条件的串
            for (int k = 0; k < 26; k++){
                if (cnt[k] < count[k]){
                    ok = false;
                    break;
                }
            } 
            if (ok){ // 更新
                res = word;      
                minLen = word.length();
            }  
        } 
        return res;
    }
}
// 借用评论中的一解
class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        Arrays.sort(words,(a,b)->a.length()-b.length());
        int[] arr = new int[26];
        int sum = 0; // 统计字母数
        for(char ch : licensePlate.toLowerCase().toCharArray()){
            if(Character.isLetter(ch)){
                arr[ch-'a']++;
                sum++;
            }
        }
        for(String s : words){
            int[] arr_ = Arrays.copyOf(arr,arr.length);
            int sum_ = 0;
            // char[] chs = s.toCharArray();
            for(char ch : s.toCharArray()){
                if(arr_[ch-'a'] > 0){
                    arr_[ch-'a']--;
                    sum_++;
                }
                if(sum_ == sum) return s; // 返回第一个符合条件串
            }
        }
        return "煞笔";
    }
}

python collections.Counter

String toLowerCase()
String toUpperCase() 

char charAt​(int index)
int length() 
char[] toCharArray()
boolean isEmpty() 

static String valueOf​(type var) 
static String valueOf​(char[] data, int offset, int count)

int indexOf​(int ch) 
int indexOf​(int ch, int fromIndex)	
int indexOf​(String str) 
int indexOf​(String str, int fromIndex) 
int lastIndexOf​(int ch) 
int lastIndexOf​(int ch, int fromIndex) 
int lastIndexOf​(String str)
int lastIndexOf​(String str, int fromIndex)

String repeat​(int count)

String replace​(char oldChar, char newChar)
String replace​(CharSequence target, CharSequence replacement)
String replaceAll​(String regex, String replacement) 
String replaceFirst​(String regex, String replacement) 

String strip() // white space 。
String stripLeading() 
String stripTrailing() 
String trim() 

String[] split​(String regex) 
String[] split​(String regex, int limit)

static String	join​(CharSequence delimiter, CharSequence... elements)
static String	join​(CharSequence delimiter, Iterable elements) 

String substring​(int beginIndex) 
String substring​(int beginIndex, int endIndex) 
CharSequence subSequence​(int beginIndex, int endIndex)