`
zhuyufufu
  • 浏览: 139505 次
  • 性别: 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就是变位词）按字典序列输出

    变位词_变位词_变位词代码_变位词伪代码_

    在编程中，处理变位词是一项常见的任务，特别是在字符串操作、算法设计和数据结构的学习中。本篇文章将深入探讨变位词的概念、如何判断两个字符串是否为变位词，以及编写变位词检测的代码和伪代码。 首先，了解变位...

    词典变位词检索系统

    词典变位词检索系统是一种基于数据结构和查找算法的应用，其主要目的是在给定的词汇库中查找与目标单词形成变位词的其他单词。变位词是通过改变单词中字母顺序而形成的新的单词，例如英语单词 "said" 和 "dais" 就是...

    变位词查询

    在编程和计算机科学领域，变位词查询是一个常见的任务，主要涉及到字符串处理和搜索算法。变位词是指那些由相同字母组成但排列顺序不同的单词，比如"tea"和"eat"，"stop"和"tops"。这些词汇在含义上可能完全不同，但...

    词典变位词检索系统.rar

    词典变位词检索系统是一种基于计算机编程技术的软件应用，主要用于帮助用户查找和分析具有相同意义但形式不同的词汇，通常在语言学习和文本处理领域中广泛应用。在这个项目中，我们关注的是一个由C语言实现的词典...

    java j2se 变位词游戏

    接着，实现变位词比较的核心算法。一个常见的方法是先对两个字符串进行排序，如果排序后的结果相同，则它们是变位词。可以使用Java的`Arrays`类中的`sort()`方法对字符数组进行排序，然后通过`equals()`方法比较两个...

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

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

    C++变位词问题分析

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

    Python实现对变位词的判断

    判断两个字符串是否为变位词是一项常见的编程任务，尤其在字符串处理和算法挑战中。在Python中，我们可以采用多种方法来实现这个功能。 1. **逐字检查**： 这种方法通过遍历第一个字符串的每个字符，并在第二个...

    经典算法题目与答案-含代码

    在编码实现方面，书籍提供了大量的练习题，如字符串处理问题，包括实现strStr()函数、判断两个字符串是否是变位词、字符串逆序、回文检测、旋转字符串等，这些问题能够帮助程序员提高对字符串操作的熟练度。...

    python实现对变位词的判断方法

    判断两个字符串是否为变位词是一个常见的编程问题，不仅出现在实际的应用场景中，也是面试时考察数据结构与算法能力的经典题目之一。 #### 二、变位词定义 变位词是指两个或多个由相同字母组成的单词或短语，但字母...

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

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

    算法学习指南.docx

    - **样题参考**：如`to-lower-case`要求将字符串转换为小写，`length-of-last-word`要求找出字符串最后一个单词的长度，`valid-anagram`检查两个字符串是否为变位词，`group-anagrams`则是将所有变位词分组，`find-...

    算法,数据结构,Python,剑指offer,机器学习,leetcode.zip

    请记得点击github工程上的star，^_^ 现在总结如下数据結構markdown格式链表及常见操作平衡查找树AVL清晰方法检测变位词Anagram构建堆二、二分调查二叉树二叉树冒泡排序英语单词拼写检查算法几个小动态规划问题Hash及...

    编程珠玑之第二章questionC 测试数据

    "第二章questionC"提及的问题是关于"求变位词"，这是一个常见的字符串处理问题，涉及到字符统计、排序以及字符串比较等基础知识。 变位词，又称为同字母异序词，是指两个或多个单词由完全相同的字母组成，但字母...

    词典检索系统

    对于变位词的检索，可以使用特殊的算法，如前缀树（Trie）、后缀数组（Suffix Array）或Burrows-Wheeler变换（BWT），这些算法能快速找到所有可能的变位词。 3. 用户界面：提供用户友好的交互方式，使用户能够方便...

    Golang字符串变位词示例详解

    在编程领域，字符串变位词（Anagram）是指由同一个单词的不同字母排列顺序构成的两个字符串。例如，"listen" 和 "silent" 就是彼此的变位词。本篇文章将详细探讨如何在 Go 语言（Golang）中判断两个字符串是否是变位...

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

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

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