這是小川的第411次更新，第443篇原創(chuàng)

看題和準備

今天介紹的是LeetCode算法題中Easy級別的第262題（順位題號是1160）。你會得到一個字符串單詞數(shù)組和一個字符串chars。如果字符串可以由字符中的字符組成（每個字符只能使用一次），則該字符串是好的。返回所有好的字符串的長度之和。

例如：

輸入：words = ["cat","bt","hat","tree"],chars ="atach"
輸出：6
說明：可以形成的字符串是"cat"和"hat"，因此答案是3 + 3 = 6。

輸入：words = ["hello","world","leetcode"],chars ="welldonehoneyr"
輸出：10
說明：可以形成的字符串是"hello"和"world"，因此答案是5 + 5 = 10。

注意：

• 1 <= words.length <= 1000

• 1 <= words[i].length , chars.length <= 100

• 所有字符串僅包含小寫英文字母。
  
  

第一種解法

題目的意思是，給了一個由英文小寫字母組成的字符串chars，在字符串數(shù)組words中，如果單詞能夠由chars中的字符組成，那么此單詞就是一個好單詞。

我們直接翻譯題目即可，將chars理解成一個數(shù)組字典，每個字母出現(xiàn)的次數(shù)計數(shù)，變成一個26位長度的int數(shù)組，接著去遍歷words中的單詞，采用同樣的原理，將單詞每個字母當做字典數(shù)組的索引，出現(xiàn)一次就減1，如果字典數(shù)組中的元素值小于0，說明當前單詞無法由chars中的字母組成，結束本此循環(huán)，直到遍歷完所有單詞。

public int countCharacters(String[] words, String chars) {
    // 獲取字典數(shù)組
    int[] dict = stringToIntegerArray(chars);
    int sum = 0;
    for (int i=0, len=words.length; i<len; i++) {
        // 復制一份字典數(shù)組，為后面的減法做準備
        int[] temp = dict.clone();
        int len2 = words[i].length();
        // 默認當前單詞是好字符串
        boolean flag = true;
        for (int j=0; j<len2; j++) {
            // 單詞中的字母不在字典中，或超過使用次數(shù)
            if (--temp[words[i].charAt(j)-'a'] < 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            sum += words[i].length();
        }
    }
    return sum;
}

/**
 * 將字符串轉為長度為26的int數(shù)組
 * @param s 字符串
 * @return 長度為26的int數(shù)組
 */
public int[] stringToIntegerArray(String s) {
    int[] arr = new int[26];
    for (int i=0, len=s.length(); i<len; i++) {
        arr[s.charAt(i)-'a']++;
    }
    return arr;
}

第二種解法

和第一種解法的思路類似，只是將第一種解法的數(shù)組復制替換成了另外一種寫法，將當前單詞也轉為一個長度為26的int數(shù)組，然后比較字典數(shù)組和單詞數(shù)組元素值的大小，如果單詞數(shù)組當前元素值大于字典數(shù)組當前元素值，則表示單詞中的某些字母不在字典中或者出現(xiàn)次數(shù)超過了字典中的次數(shù)。

public int countCharacters2(String[] words, String chars) {
    // 獲取字典數(shù)組
    int[] dict = stringToIntegerArray(chars);
    int sum = 0, len = words.length, len2 = dict.length;
    for (int i=0; i<len; i++) {
        // 將單詞也轉為int數(shù)組
        int[] temp = stringToIntegerArray(words[i]);
        boolean flag = true;
        for (int j=0; j<len2; j++) {
            if (temp[j] > dict[j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            sum += words[i].length();
        }
    }
    return sum;
}

/**
 * 將字符串轉為長度為26的int數(shù)組
 * @param s 字符串
 * @return 長度為26的int數(shù)組
 */
public int[] stringToIntegerArray(String s) {
    int[] arr = new int[26];
    for (int i=0, len=s.length(); i<len; i++) {
        arr[s.charAt(i)-'a']++;
    }
    return arr;
}

小結

算法專題目前已更新LeetCode算法題文章268+篇，公眾號對話框回復【數(shù)據(jù)結構與算法】、【算法】、【數(shù)據(jù)結構】中的任一關鍵詞，獲取系列文章合集。

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發(fā)就是對我最大的回報和支持！