package y2019.Algorithm.array;

import java.util.*;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: CommonChars

 * @Author: xiaof

 * @Description: 1002. Find Common Characters

 * Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings

 * within the list (including duplicates).

 * For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times

 * in the final answer.

 * You may return the answer in any order.

 *

 * Input: ["bella","label","roller"]

 * Output: ["e","l","l"]

 *

 * @Date: 2019/7/4 11:07

 * @Version: 1.0

 */

public class CommonChars {

    public List<String> solution(String[] A) {

        List<String> result = new ArrayList<>();

        int[] nums = new int[26]; //英文一共26个字符，并且是小写的

        Arrays.fill(nums, Integer.MAX_VALUE);

        //遍历所有的字符，根据小标放入集合中

        for(String aTemp : A) {

            //依次遍历所有字符

            char tempC[] = aTemp.toCharArray();

            int[] cnt = new int[26];

            //第一次统计每个单词中出现的次数

            for(int j = 0; j < tempC.length; ++j) {

                cnt[tempC[j] - 'a']++;

            }

            //第二次我们过滤掉，每二个单词中出现的最小次数，比如第一个单词出现10次，但是第二个单词出现1次，那么都出现的次数也就是1次

            for(int i = 0; i < nums.length; ++i) {

                nums[i] = Math.min(nums[i], cnt[i]);

            }

        }

        //最后统计结果

        for(int i = 0; i < nums.length; ++i) {

            for(int j = 0; j < nums[i]; ++j) {

                //如果出现多处，那么放入多处

                result.add("" + (char) ('a' + i));

            }

        }

        //如果每个字符中都出现过，那么必须是3的倍数次

        return result;

    }

    public List<String> commonChars(String[] A) {

        List<String> ans = new ArrayList<>();

        int[] count = new int[26];

        Arrays.fill(count, Integer.MAX_VALUE);

        for (String str : A) {

            int[] cnt = new int[26];

            for (int i = 0; i < str.length(); ++i) { ++cnt[str.charAt(i) - 'a']; } // count each char's frequency in string str.

            for (int i = 0; i < 26; ++i) { count[i] = Math.min(cnt[i], count[i]); } // update minimum frequency.

        }

        for (char c = 'a'; c <= 'z'; ++c) {

            while (count[c - 'a']-- > 0) { ans.add("" + c); }

        }

        return ans;

    }

    public static void main(String args[]) {

        String as[] = {"bella","label","roller"};

        CommonChars fuc = new CommonChars();

        System.out.println(fuc.solution(as));

    }

}