`
zhuyufufu
  • 浏览: 135143 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

变位词算法

算法面试变位词数据结构容器集合 
阅读更多
变位词
   一种把某个词或句子的字母的位置（顺序）加以改换所形成的新词，英文叫做anagram，词典把这个词翻译成“变位词”。

  
   最近参加了一个面试，其中一道上机题目就是有关变位词的。

   题目描述大致如下：
    1.给出一个两个字符串互为变位词的相似度算法。当他们为变位词的时候输出1.0；当他们长度不同且没有相同字母时输出0；其他情况给出一个规则输出一个0到1之间的浮点数。
    2.有一个文件其中有18万个单词，输出变位词集合长度超过8的变位词集合到一个文件中。
   这道题目的考点有四个：
   1.变位词算法的设计
   2.变位词相似度算法的设计
   3.Java文件流读写
   4.java容器的使用情况

   由于在前一道题目上时间分配不合理，我没有充足的时间完成代码：相似度算法、文件流输出没有实现，变位词集合查找算法设计的也有缺陷，单元测试根本没写。

   虽然从面试的角度看我这个问题解决的很失败，但是生活还要继续。在本文中，我再次完成这道题目记录我这次失败的机试。

   按照我的直觉，相似度算法是最麻烦的，因为它没有一个精确的定义。因此，最后再解决它。

  第一步：变位词算法的设计
     理解变位词：从变位词概念上讲，词语是忽略大小写的；两个词语的字母及字母的数量是相同的；相同的单词当然是变位词。
     这样的话，变位词判断至少有两种方法：
         1.对两个词语按字母顺序排序，再比较其是否相同，相同则为变位词。
         2.把两个词语按字母-字母个数分解到两个键值对(map)中，再比较两个map。

     下面给出变位词排序算法的Java实现： 
package com.zas.anagram;

/**
 * 变位词算法设计
 * @author zas
 *
 */
public class Anagram {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(Anagram.isAnagram(null, null));
		System.out.println(Anagram.isAnagram("", ""));
		System.out.println(Anagram.isAnagram("", null));
		System.out.println(Anagram.isAnagram(null, ""));
		System.out.println(Anagram.isAnagram(null, "cba"));
		System.out.println(Anagram.isAnagram("cba", null));
		System.out.println(Anagram.isAnagram("abc", "cba"));
		System.out.println(Anagram.isAnagram("abc", "cbaa"));
		System.out.println(Anagram.isAnagram("abc", "cbc"));
	}

	/**
	 * 判断两个单词是否互为变位词
	 * @param string
	 * @param string2
	 * @return true/false
	 */
	public static boolean isAnagram(String wordA, String wordB) {
		//异常情况处理
		if(null == wordA && null == wordB){
			return true;
		}
		if(false == handleNull(wordA, wordB)){
			return false;
		}
		return isAnagramBySort(wordA, wordB);
	}
	

	/**
	 * 处理异常情况 返回 true表示要继续处理 false表示不为变位词
	 * @param wordA
	 * @param wordB
	 * @return true/false
	 */
	private static boolean handleNull(String wordA, String wordB) {
		//一个为空，另一个不为空不是变位词
		if(null == wordA && null != wordB){
			return false;
		}
		if(null == wordB && null != wordA){
			return false;
		}
		//长度不同不为变位词
		if(wordA.length() != wordB.length()){
			return false;
		}
		return true;
	}

	/**
	 * 通过排序后比较其是否相同判断是否为变位词
	 * @param wordA
	 * @param wordB
	 * @return true/false
	 */
	private static boolean isAnagramBySort(String wordA, String wordB) {
		//获取两个单词的小写复本
		wordA = wordA.toLowerCase();
		wordB = wordB.toLowerCase();
		//对两个单词按字母大小顺序排序
		wordA = sort(wordA);
		wordB = sort(wordB);
		
		if(wordA.equals(wordB)){
			return true;
		}
		return false;
	}

	/**
	 * 按字母顺序排序字符串
	 * @param wordA
	 * @return
	 */
	private static String sort(String word) {
		char[] charArray = word.toCharArray();
		//排序基本为小数据量的，因此采用冒泡、选择、插入中的一种，这里选择选择排序
		for (int i = 0; i < charArray.length; i++) {
			//内层循环找到未排序的最小字母
			int selectedIndex = i;
			for (int j = 0; j < charArray.length; j++) {
				if(charArray[selectedIndex] > charArray[j]){
					selectedIndex = j;
				}
			}
			if(selectedIndex != i){
				char tempForSwap = charArray[selectedIndex];
				charArray[selectedIndex] = charArray[i];
				charArray[i] = tempForSwap;
			}
		}
		return String.valueOf(charArray);
	}
	
}

 
  
    通过map来实现变位词判断: 
package com.zas.anagram;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * 变位词算法设计
 * @author zas
 *
 */
public class Anagram {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(Anagram.isAnagram(null, null));
		System.out.println(Anagram.isAnagram("", ""));
		System.out.println(Anagram.isAnagram("", null));
		System.out.println(Anagram.isAnagram(null, ""));
		System.out.println(Anagram.isAnagram(null, "cba"));
		System.out.println(Anagram.isAnagram("cba", null));
		System.out.println(Anagram.isAnagram("abc", "cba"));
		System.out.println(Anagram.isAnagram("abc", "cbaa"));
		System.out.println(Anagram.isAnagram("abc", "cbc"));
	}

	/**
	 * 判断两个单词是否互为变位词
	 * @param string
	 * @param string2
	 * @return true/false
	 */
	public static boolean isAnagram(String wordA, String wordB) {
		//异常情况处理
		if(null == wordA && null == wordB){
			return true;
		}
		if(false == handleNull(wordA, wordB)){
			return false;
		}
		//return isAnagramBySort(wordA, wordB);
		return isAnagramByMap(wordA, wordB);
	}
	

	/**
	 * 处理异常情况 返回 true表示要继续处理 false表示不为变位词
	 * @param wordA
	 * @param wordB
	 * @return true/false
	 */
	private static boolean handleNull(String wordA, String wordB) {
		//一个为空，另一个不为空不是变位词
		if(null == wordA && null != wordB){
			return false;
		}
		if(null == wordB && null != wordA){
			return false;
		}
		//长度不同不为变位词
		if(wordA.length() != wordB.length()){
			return false;
		}
		return true;
	}

	/**
	 * 通过排序后比较其是否相同判断是否为变位词
	 * @param wordA
	 * @param wordB
	 * @return true/false
	 */
	private static boolean isAnagramBySort(String wordA, String wordB) {
		//获取两个单词的小写复本
		wordA = wordA.toLowerCase();
		wordB = wordB.toLowerCase();
		//对两个单词按字母大小顺序排序
		wordA = sort(wordA);
		wordB = sort(wordB);
		
		if(wordA.equals(wordB)){
			return true;
		}
		return false;
	}

	/**
	 * 按字母顺序排序字符串
	 * @param wordA
	 * @return
	 */
	private static String sort(String word) {
		char[] charArray = word.toCharArray();
		//排序基本为小数据量的，因此采用冒泡、选择、插入中的一种，这里选择选择排序
		for (int i = 0; i < charArray.length; i++) {
			//内层循环找到未排序的最小字母
			int selectedIndex = i;
			for (int j = 0; j < charArray.length; j++) {
				if(charArray[selectedIndex] > charArray[j]){
					selectedIndex = j;
				}
			}
			if(selectedIndex != i){
				char tempForSwap = charArray[selectedIndex];
				charArray[selectedIndex] = charArray[i];
				charArray[i] = tempForSwap;
			}
		}
		return String.valueOf(charArray);
	}
	
	/**
	 * 通过 字母-字母个数 键值对来判断变位词
	 * @param wordA
	 * @param wordB
	 * @return true false;
	 */
	private static boolean isAnagramByMap(String wordA, String wordB) {
		Map<Character, Integer> mapForWordA = getWordMap(wordA);
		Map<Character, Integer> mapForWordB = getWordMap(wordB);
		//字母的个数不同肯定不是变位词
		if(mapForWordA.size() != mapForWordB.size()){
			return false;
		}
		//迭代mapForWordA的字母 并在mapForWordB中获得对应的字母个数 若不同则不是变位词
		Set<Character> key = mapForWordA.keySet();
        for (Iterator<Character> it = key.iterator(); it.hasNext();) {
        	Character c = (Character) it.next();
        	Integer charCountA = mapForWordA.get(c);
        	Integer charCountB = mapForWordB.get(c);
        	if(charCountA != charCountB){
        		return false;
        	}
        }
		return true;
	}

	/**
	 * 获得一个字符串的字母-字母个数键值对
	 * @param wordA
	 * @return
	 */
	private static Map<Character, Integer> getWordMap(String word) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		char[] charArray = word.toCharArray();
		for (int i = 0; i < charArray.length; i++) {
			Character c = charArray[i];
			Integer charCount = map.get(c);
			if(null == charCount){
				charCount = 1;
			}else{
				charCount = charCount + 1;
			}
			map.put(c, charCount);
		}
		return map;
	}
}



从一个词典列表文件中读取单词到List， 再把这个单词List分解成变位词集合列表，根据条件查找变位词集合列表子集，输出变位词列表到文件的Java实现如下： 
package com.zas.anagram;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 变位词算法设计
 * @author zas
 *
 */
public class Anagram {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(Anagram.isAnagram(null, null));
		System.out.println(Anagram.isAnagram("", ""));
		System.out.println(Anagram.isAnagram("", null));
		System.out.println(Anagram.isAnagram(null, ""));
		System.out.println(Anagram.isAnagram(null, "cba"));
		System.out.println(Anagram.isAnagram("cba", null));
		System.out.println(Anagram.isAnagram("abc", "cba"));
		System.out.println(Anagram.isAnagram("abc", "cbaa"));
		System.out.println(Anagram.isAnagram("abc", "cbc"));
	}

	/**
	 * 判断两个单词是否互为变位词
	 * @param string
	 * @param string2
	 * @return true/false
	 */
	public static boolean isAnagram(String wordA, String wordB) {
		//异常情况处理
		if(null == wordA && null == wordB){
			return true;
		}
		if(false == handleNull(wordA, wordB)){
			return false;
		}
		//return isAnagramBySort(wordA, wordB);
		return isAnagramByMap(wordA, wordB);
	}
	

	/**
	 * 处理异常情况 返回 true表示要继续处理 false表示不为变位词
	 * @param wordA
	 * @param wordB
	 * @return true/false
	 */
	private static boolean handleNull(String wordA, String wordB) {
		//一个为空，另一个不为空不是变位词
		if(null == wordA && null != wordB){
			return false;
		}
		if(null == wordB && null != wordA){
			return false;
		}
		//长度不同不为变位词
		if(wordA.length() != wordB.length()){
			return false;
		}
		return true;
	}

	/**
	 * 通过排序后比较其是否相同判断是否为变位词
	 * @param wordA
	 * @param wordB
	 * @return true/false
	 */
	private static boolean isAnagramBySort(String wordA, String wordB) {
		//获取两个单词的小写复本
		wordA = wordA.toLowerCase();
		wordB = wordB.toLowerCase();
		//对两个单词按字母大小顺序排序
		wordA = sort(wordA);
		wordB = sort(wordB);
		
		if(wordA.equals(wordB)){
			return true;
		}
		return false;
	}

	/**
	 * 按字母顺序排序字符串
	 * @param wordA
	 * @return
	 */
	private static String sort(String word) {
		char[] charArray = word.toCharArray();
		//排序基本为小数据量的，因此采用冒泡、选择、插入中的一种，这里选择选择排序
		for (int i = 0; i < charArray.length; i++) {
			//内层循环找到未排序的最小字母
			int selectedIndex = i;
			for (int j = 0; j < charArray.length; j++) {
				if(charArray[selectedIndex] > charArray[j]){
					selectedIndex = j;
				}
			}
			if(selectedIndex != i){
				char tempForSwap = charArray[selectedIndex];
				charArray[selectedIndex] = charArray[i];
				charArray[i] = tempForSwap;
			}
		}
		return String.valueOf(charArray);
	}
	
	/**
	 * 通过 字母-字母个数 键值对来判断变位词
	 * @param wordA
	 * @param wordB
	 * @return true false;
	 */
	private static boolean isAnagramByMap(String wordA, String wordB) {
		Map<Character, Integer> mapForWordA = getWordMap(wordA);
		Map<Character, Integer> mapForWordB = getWordMap(wordB);
		//字母的个数不同肯定不是变位词
		if(mapForWordA.size() != mapForWordB.size()){
			return false;
		}
		//迭代mapForWordA的字母 并在mapForWordB中获得对应的字母个数 若不同则不是变位词
		Set<Character> key = mapForWordA.keySet();
        for (Iterator<Character> it = key.iterator(); it.hasNext();) {
        	Character c = (Character) it.next();
        	Integer charCountA = mapForWordA.get(c);
        	Integer charCountB = mapForWordB.get(c);
        	if(charCountA != charCountB){
        		return false;
        	}
        }
		return true;
	}

	/**
	 * 获得一个字符串的字母-字母个数键值对
	 * @param wordA
	 * @return
	 */
	private static Map<Character, Integer> getWordMap(String word) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		char[] charArray = word.toCharArray();
		for (int i = 0; i < charArray.length; i++) {
			Character c = charArray[i];
			Integer charCount = map.get(c);
			if(null == charCount){
				charCount = 1;
			}else{
				charCount = charCount + 1;
			}
			map.put(c, charCount);
		}
		return map;
	}
	
	/**
	 * 从文件中获取词典列表
	 * @param path
	 * @return List<String>
	 */
	private static List<String> getWordsListFromFile(String path) {
		List<String> wordList = new ArrayList<String>();
		File file = new File(path);
		FileReader fr = null;
		BufferedReader br = null;
		try{
			fr = new FileReader(file);
			br = new BufferedReader(fr);
			String s;
			while((s = br.readLine()) != null){
				//去首尾空白
				s = s.trim();
				wordList.add(s);
			}
		}catch(FileNotFoundException e){
			e.printStackTrace();
		}catch (Exception e) {
			e.printStackTrace();
		}finally{
			if(br != null){
				try {
					br.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			if(fr != null){
				try {
					fr.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
		
		return wordList;
	}
	
	/**
	 * 获取所有变位词集合列表
	 * @param wordList
	 * @return
	 */
	private static Map<String, List<String>> getAnagramCollectionMap(List<String> wordList) {
		Map<String, List<String>> anagramCollectionMap = new HashMap<String, List<String>>();
		while(wordList.size() > 0){
			String word = wordList.remove(0);
			//将单词存入变位词集合map中
			//这里有两种算法，一种是把单词排序之后放入map这样就不需要遍历map
			//另一种是遍历map的key判断它是否和该单词互为变位词
			//这里采用第一种
			String sortedWord = sort(new String(word).toLowerCase());
			List<String> list = anagramCollectionMap.get(sortedWord);
			if(list == null){
				list = new ArrayList<String>();
			}
			list.add(word);
			anagramCollectionMap.put(sortedWord, list);
		}
		return anagramCollectionMap;
	}
	
	/**
	 * 根据某种条件从map集中获取符合条件的列表 可以考虑实现一个说明模式
	 * 为了演示简便，给出获取特定大小变位词集合的实现
	 * @param anagramCollectionMap
	 * @return
	 */
	private static Map<String, List<String>> getAnagramCollectionMapByCondition(Map<String, List<String>> anagramCollectionMap, int size) {
		Map<String, List<String>> resultMap = new HashMap<String, List<String>>();
		Set<String> key = anagramCollectionMap.keySet();
        for (Iterator<String> it = key.iterator(); it.hasNext();) {
        	String str = (String) it.next();
        	List<String> list= anagramCollectionMap.get(str);
        	if(list.size() == size){
        		resultMap.put(str, list);
        	}
        }
		return resultMap;
	}
	
	/**
	 * 向文件中输出变位词集合列表
	 * @param path
	 * @return 
	 */
	private static void writeWordsListToFile(String path, Map<String, List<String>> anagramCollectionMap) {
		File file = new File(path);
		FileWriter fw = null;
		BufferedWriter bw = null;
		try{
			fw = new FileWriter(file);
			bw = new BufferedWriter(fw);
			Set<String> key = anagramCollectionMap.keySet();
	        for (Iterator<String> it = key.iterator(); it.hasNext();) {
	        	String str = (String) it.next();
	        	List<String> list= anagramCollectionMap.get(str);
	        	bw.write(str + list.toString());
	        	bw.newLine();
	        }
		}catch(FileNotFoundException e){
			e.printStackTrace();
		}catch (Exception e) {
			e.printStackTrace();
		}finally{
			if(bw != null){
				try {
					bw.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			if(fw != null){
				try {
					fw.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
	}
}




这次的实现比去面试时思路清晰多了！


变位词相似度算法暂时还没思路，后面再写篇文章补上吧！
分享到：
| 由打篮球投篮练习想到的
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    算法设计ACM 变位词

    输入N和一个要查找的字符串，以下有N个字符串，我们需要找出其中的所有待查找字符串的变位词（例如eat,eta,aet就是变位词）按字典序列输出

    词典变位词检索系统的C++实现

    词典变位词检索系统 问题描述：在英文中，把某个单词字母的位置加以改变所形成的新字词，成为anagram（变位词）。譬如said（say的过去式）就有dais（讲台）这个变位词。在中世纪，这种文字游戏盛行于欧洲各地，当时...

    C++变位词问题分析

    由变位词可以引申出几个算法问题，包括字符串包含问题，比较两个字符串是否是变位词，以及找出字典中变位词集合的问题。 一、字符串包含问题 (1) 问题描述：存在字符串1和字符串2，假设字符串2相对较短，如何快速地...

    数据结构题目：词典检索系统

    不妨译为变位词。辔如said(say的过去式)就有dais(讲台)这个变位词。在中世纪，这种 文字游戏盛行于欧洲各地，当时很多人相信一种神奇的说法，认为人的姓名倒着拼所产生 的意义可能跟本性和命运有某种程度的关联。...

    算法/数据结构/Python/剑指offer/机器学习/leetcode

    三种方法检测变位词Anagram 构建堆 二分查找 二叉查找树 二叉树 冒泡排序 英语单词拼写检查算法 几个小的动态规划问题 Hash及常见操作 插入排序 归并排序 解析树ParseTree 队列 快排 基数排序 一些...

    基于Python实现的数据结构与算法完整源代码+超详细注释(包含46个作业项目).zip

    01_变位词问题 02_python数据类型的性能 03_python实现ADT Stack 04_栈的应用1括号匹配 05_栈的应用2十进制转二进制 06_栈的应用3中缀转后缀表达式 07_栈的应用4后缀表达式求值 08_python实现ADT Queue 09_队列的...

    编程珠玑 第二版 修订版

    2.8　变位词程序的实现（边栏） 18 第3章　数据决定程序结构 21 3.1　一个调查程序 21 3.2　格式信函编程 23 3.3　一组示例 25 3.4　结构化数据 26 3.5　用于特殊数据的强大工具 27 3.6　原理 28 3.7　习题 29 3.8　...

    leetcode答案-book_pearls_note:编程珠玑第二版，笔记

    leetcode 答案 programming Pearls Second Edition 确实是一本可以影响整个职业生涯的书 位图数据结构： 最开始了解这个结构，是在刷...leetcode里有许多变位词的题，都是标识算法的衍生。 使用等价关系替换问题

    LeetCode解题总结

    3.13 变位词 3.14 简化系统路径 3.15 最后一个单词的长度 3.16 反转字符串中的单词 3.16.1 字符串前后和中间可能存在多个空格 3.16.2 不存在前后和中间的多余空格 3.17 一个编辑距离 4. 栈 4.1 验证括号的正确性 4.2...

Magicbox
Global site tag (gtag.js) - Google Analytics