更新字典(Updating a Dictionary)

Submit Status

Description

In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.

Each dictionary is formatting as follows:

Each key is a string of lower-case letters, and each value is a non-negative integer without leading zeros or prefix `+'. (i.e. -4, 03 and +77 are illegal). Each key will appear at most once, but keys can appear in any order.

Input 

The first line contains the number of test cases T ( T1000). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.

WARNING: there are no restrictions on the lengths of each key and value in the dictionary. That means keys could be really long and values could be really large.

Output 

For each test case, print the changes, formatted as follows:

• First, if there are any new keys, print `+' and then the new keys in increasing order (lexicographically), separated by commas.
• Second, if there are any removed keys, print `-' and then the removed keys in increasing order (lexicographically), separated by commas.
• Last, if there are any keys with changed value, print `*' and then these keys in increasing order (lexicographically), separated by commas.

If the two dictionaries are identical, print `No changes' (without quotes) instead.

Print a blank line after each test case.

Sample Input 

3
{a:3,b:4,c:10,f:6}
{a:3,c:5,d:10,ee:4}
{x:1,xyz:123456789123456789123456789}
{xyz:123456789123456789123456789,x:1}
{first:1,second:2,third:3}
{third:3,second:2}
  

Sample Output 

+d,ee
-b,f
*c

No changes

-first
  

【分析】

       用两个Map分别存储旧字典和新字典的键值，为了方便，同时使用2个链表对应存储键，这样遍历Map时就只需要用到这两个链表，用3个链表存储3种情况的值（新增键、删除键、修改键）。如果新字典的Map中有一个键不被旧字典的Map包含，则说明是新增键，并把该键存储在对应链表中；如果包含，还要判断对应是值是否相等，如果相等则不予以处理，如果不相等，则说明该键是修改键，并把该键存储在对应链表中；如果旧字典的Map中有一个键不被新字典的Map包含，则说明该键是删除键，并把该键存储在对应链表中；最后判断3个链表是否为空，如果为空，说明字典并没有发生改变。

【注意】

1、要注意输入的字典可能为空的情况，所以在处理字符串时，需要特别注意。否则结果可能因为访问越界容易出现Runtime error 的错误。

2、每个测试结果的最后均有一行空行。

3、输出结果需要按字典序从小到大排列，所以存储键的那两个链表在存储完所有键之后需要进行排序，那样从中取键时加入到结果链表中仍可以保持字典序，这样就可以不用对结果链表进行排序。

用java语言编写程序，代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int t = input.nextInt();
		
		input.nextLine();
		
		TreeMap<String, String> tm1 = new TreeMap<String, String>();
		TreeMap<String, String> tm2 = new TreeMap<String, String>();
		ArrayList<String> l1 = new ArrayList<String>();
		ArrayList<String> l2 = new ArrayList<String>();
		for(int i = 0; i < t; i++) {
			String s1 = input.nextLine();
			String s2 = input.nextLine();
			
			tm1.clear();
			tm2.clear();
			l1.clear();
			l2.clear();
			
			getValue(s1, tm1, l1);
			getValue(s2, tm2, l2);
			
			output(tm1, l1, tm2, l2);
		}
	}
	
	public static void getValue(String s, TreeMap<String, String> tm, ArrayList<String> list) {
		/*String[] sarr = s.substring(1, s.length() - 1).split(",");
		for(int j = 0; j < sarr.length; j++) {
			String[] stemp = sarr[j].split(":");
			tm.put(stemp[0], stemp[1]);
			list.add(stemp[0]);
		}*/
		int len = s.length();
		String strKey = "";
		String strValue = "";
		String temp = "";
		for(int i = 0; i < len; i++) {
			char c = s.charAt(i);
			if(c == ':') {
				if(!temp.equals("")) {
					strKey = "";
					strKey = "" + temp;
					list.add(strKey);
					temp = "";					
				}
			}
			else if(c == ',' || c == '}') {
				if(!temp.equals("")) {
					strValue = "";
					strValue = "" + temp;
					tm.put(strKey, strValue);
					//System.out.println(strKey + "...." + strValue);
					temp = "";					
				}
			}
			else if(c != '{' && c != '}') {
				temp = temp + c;
			}
		}
		Collections.sort(list);
	}
	
	public static void output(TreeMap<String, String> tm1, ArrayList<String> l1,
			TreeMap<String, String> tm2, ArrayList<String> l2) {		
		ArrayList<String> list1 = new ArrayList<String>();
		ArrayList<String> list2 = new ArrayList<String>();
		ArrayList<String> list3 = new ArrayList<String>();
		
		for(int i = 0; i < l2.size(); i++) {
			String key = l2.get(i);
			String value = tm2.get(key);
			
			if(tm1.containsKey(key)) {
				if(!tm1.get(key).equals(value))
					list3.add(key);
			}
			else {
				list1.add(key);
			}
		}
		
		for(int i = 0; i < l1.size(); i++) {
			String key = l1.get(i);
			if(!tm2.containsKey(key))
				list2.add(key);
		}
		
		if(list1.size() == 0 && list2.size() == 0 && list3.size() == 0)
			System.out.println("No changes");
		else {
			print('+', list1);
			print('-', list2);
			print('*', list3);			
		}
		System.out.println();
	}
	
	public static void print(char c, ArrayList<String> list) {
		if(list.size() != 0) {
			System.out.print(c + list.get(0));
			for(int i = 1; i < list.size(); i++)
				System.out.print("," + list.get(i));
			System.out.println();
		}
	}
}