【leetcode】Anagrams

• 题目
  • Given an array of strings, return all groups of strings that are anagrams.
  • 首先简单介绍一下Anagram（回文构词法）。Anagrams是指由颠倒字母顺序组成的单词，比如"tea"会变成"eat"。

    For example:

    Input:["tea","and","ate","eat"]

    Output:???["tea","ate","eat"]

• 解题思路
  • 定义一个Arraylist ar存储所有字符串排序后的字符串
    • ar:["aet", "aet", "aet", "adn"]
  • 定义一个list[strs.length]标记字符串是否要被输出，1：被输出
  • 定义一个tmp，记录同样字符串的个数，大于1被输出
  • 两层循环，两两比较，相同的话，tmp+1，相应list位标记为1，如果从第i位算起，后面都没有与第i个字符串相同的话，第i位list重新标记为0.
  • list标记位为：1 1 1 0
  • 将相应位的string数组输出即可
• 代码

  package leetcode;

  ? ?

  import java.util.ArrayList;

  import java.util.Arrays;

  import java.util.Iterator;

  ? ?

  /**

  * Given an array of strings, return all groups of strings that are anagrams.

  *

  * Note: All inputs will be in lower-case.

  */

  ? ?

  public class Anagrams {

  public static void main(String[] args) {

  String[] strs = new String[] { "tea", "eat", "ate", "and" };

  Anagrams anagrams = new Anagrams();

  ArrayList result = new ArrayList<>();

  result = anagrams.anagrams(strs);

  System.out.println("result‘s length is " + result.size());

  System.out.print("result is " + "[ ");

  ? ?

  Iterator iterator = result.iterator();

  while (iterator.hasNext()) {

  Object object = (Object) iterator.next();

  System.out.print("\"" + object + "\"" + "," + " ");

  }

  System.out.println("]");

  }

  ? ?

  public ArrayList<String> anagrams(String[] strs) {

  ArrayList<String> ret = new ArrayList<String>();

  ArrayList<String> ar = new ArrayList<String>();

  for (String s : strs) {

  char[] c = s.toCharArray();

  Arrays.sort(c);

  ar.add(new String(c));

  }

  int[] list = new int[strs.length];

  int tmp = 0;

  for (int i = 0; i < ar.size(); i++) {

  if (list[i] == 0) {

  list[i] = 1;

  tmp = 1;

  for (int j = i + 1; j < ar.size(); j++) {

  if (list[j] == 0 && ar.get(i).equals(ar.get(j))) {

  list[j] = 1;

  tmp++;

  }

  }

  if (tmp == 1) {

  list[i] = 0;

  }

  }

  }

  for (int i = 0; i < list.length; i++) {

  if (list[i] == 1)

  ret.add(strs[i]);

  }

  return ret;

  }

  }

• ?

【leetcode】Anagrams

原文：http://www.cnblogs.com/keedor/p/4366723.html