经典面试题13 - Anagram

Anagram

问题
这里有字符串A 和 字符串B，需要删除多少字符才能让两个字符串互为Anagram？

例子：字符串A是 cde ，字符串B 是abc
我们需要在字符串中删除以下字符让两者互为Anagram。

• 从字符串 cde 中移除 d 和 e，得到 c 。
• 从字符串 abc 中移除 a 和 b，得到 c 。

我们共删除了 4 个字符。

Anagram 是指调整一个单词或短语的字母顺序后组成另外 一个单词或短语,通常前后两者的关系有点讽刺意味。

解答
字符串互为Anagram的前提是 字符串内包含的字符一样，且个数一样，只是顺序有可能不一样。

理解了这个问题解题思路就呼之欲出，遍历两个字符串，统计每个字符出现的次数，然后相同字符次数互减，剩下的都是要移除的字符。

下面是 Java 版的代码样例。

import java.io.*;
import java.util.*;
import java.text.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        int[] array = new int[26];
        for(int i=0;i<s1.length();i++) 
            array[s1.charAt(i)-'a']++;
        for(int i=0;i<s2.length();i++) 
            array[s2.charAt(i)-'a']--;
        int count = 0;
        for(int i=0;i<26;i++) 
            count+=array[i]<0 ? -array[i] : array[i];
        System.out.println(count);
    }
}

推荐阅读

经典面试100题 - 持续更新中