一个字符串是匹配算法题的解题思路

迷南。 2022-03-20 05:50 164阅读 0赞

package org.test.algo;
    
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    import java.util.TreeMap;
    
    /**
     * 原题：
      假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配，
     比如：abcda和adabc,由于出现的字符个数都是相同，只是顺序不同，
     所以这两个字符串是匹配的。要求高效！
     * @author lushuaiyin
     我的解答思路：
     把2个字符串都遍历一次，每个字符出现的次数放入一个TreeMap（注：TreeMap自动排序）。
     这样可以把字符串每次字符出现的次数信息都拿到了。
     之后不用再遍历map去比较是不是一致，只要使用java自带的方法m1.equals(m2)
     就可以判断map的信息是不是一致（不能用m1==m2来判断！）。这样我之便利一次就能判断出结果。
     
     测试打印结果：
     
     m1:
    key:a,value:2
    key:b,value:1
    key:c,value:3
    key:d,value:1
    key:e,value:1
    -------------
    m2:
    key:a,value:2
    key:b,value:1
    key:c,value:3
    key:d,value:1
    key:e,value:1
    ------------------
    m1==m2,结果匹配
    m1:
    key:a,value:2
    key:b,value:1
    key:c,value:3
    key:d,value:1
    key:e,value:1
    -------------
    m2:
    key:a,value:1
    key:b,value:1
    key:c,value:2
    key:d,value:1
    key:e,value:1
    key:f,value:1
    key:g,value:1
    ------------------
    m1!=m2,结果不匹配！
    
     */
    public class StrMatchTest {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		String str1="aabcccde";
    		String str2="caebcdac";
    		String str3="caebcdfg";
    		StrMatchTest.isMatch(str1,str2);
    		StrMatchTest.isMatch(str1,str3);
    	}
    	
    	public static boolean isMatch(String a,String b){
    		boolean flag=false;
    		if(a==null||b==null){
    			
    		}else if(a.trim().equals("")||b.trim().equals("")){
    			
    		}else{
    			char[] ar=a.trim().toCharArray();
    			char[] br=b.trim().toCharArray();
    			if(ar.length!=br.length){
    				
    			}else{
    				Map m1=new TreeMap();
    				Map m2=new TreeMap();
    				
    				for(int i=0;i<ar.length;i++){
    					int counta=(Integer) ((m1.get(ar[i])==null)?0:m1.get(ar[i]));
    					m1.put(ar[i], counta+1);
    				}
    				for(int j=0;j<br.length;j++){
    					int countb=(Integer) ((m2.get(br[j])==null)?0:m2.get(br[j]));
    					m2.put(br[j], countb+1);
    				}
    				System.out.println("m1:");
    				StrMatchTest.printMap(m1);
    				System.out.println("-------------");
    				
    				System.out.println("m2:");
    				StrMatchTest.printMap(m2);
    				System.out.println("------------------");
    				if(m1.equals(m2)){
    					System.out.println("m1==m2,结果匹配");
    					flag=true;
    				}else{
    					System.out.println("m1!=m2,结果不匹配！");
    				}
    				
    			}
    			
    			
    		}
    		
    		return flag;
    	}
    	
    	
    	public static void printMap(Map m){
    		if(m==null){
    			System.out.println("map is null");
    		}else{
    			for(Iterator it=m.keySet().iterator();it.hasNext();){
    				Object key=(Object)it.next();  
    	            Object value=(Object)m.get(key);  
    	            System.out.println("key:"+key.toString()+",value:"+value.toString()); 
    			}
    		}
    	}
    }