Cracking the Interview - Strings

Making Anagram

Alice最近开始研究密码学,她发现变形词非常有用。两个字符串互为变形词,如果它们具有相同的字符。例如,字符串bacdcdcbac互为变形词, 而字符串bacdc"dcbad则不是。
Alice决定采用一种加密方法,它依赖于使得两个大字符串成为变形词最少所要删除字符的字符总数。她需要你的帮助计算这个数。
给定两个字符串,帮助她计算出需要删除的最少字符数使它们成为变形词,两个字符串中的任意字符都可以被删除。

输入格式
两行,每行包含一个字符串A和B。

约束条件*
1 <= A,B的长度 <= 10000
A和B只包含小写的字母。

Output Format
一个整数,表示最少删除的字母个数。

输入样例:

cde
abc

输出样例 :

4

解释 :
我们需要删掉4个字符使它们成为变形词,从第一个字符串中删掉 ‘d’和 ‘e’,从第二个字符串中删掉 'b' 和 ‘a’。

** Java Solution **

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
/*Using ACSII
 If the input is not ASCII, the size of alphabet will be different
*/
public class Solution {
  public static int numberNeeded(String first, String second) {
       int[] alphabet = new int[26];
       for(int i=0;i<first.length(); i++){
      //Add the number of each character
       alphabet[first.charAt(i)-'a']++;}
       for(int i=0;i<second.length(); i++){
     //minus the character in the second String
       alphabet[second.charAt(i)-'a']--;}
       int ret = 0;
     // m may be smaller than zero, so using Math.abs
       for (int m: alphabet) ret += Math.abs(m);
       return ret;
    }
        
     

  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        System.out.println(numberNeeded(a, b));
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容