程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Lettocde_242_Valid Anagram

Lettocde_242_Valid Anagram

編輯:關於C++

 


Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = anagram, t = nagaram, return true.
s = rat, t = car, return false.

思路:

(1)題意為給定兩個字符串,要求判定其中的一個字符串能否通過移位得到另一個字符串。

(2)該題考察的是兩個字符串組成的字符是否完全一致。下面給出了三種不同的解題方法,方法一:將兩個字符串轉為字符數組,通過Arrays.sort()方法對字符數組進行排序,然後判斷兩字符數組組成的字符串是否完全一致來得到答案;方法二:借用map來保存其中一個字符串中的字符及其個數,然後遍歷另一個字符串對應的字符數組,判定遍歷到的字符是否存在map中,若不存在返回false,若存在,則當前字符在map中的值減1,遍歷完即得到結果;方法三:借用一個整形數組來實現,該方法效率最好,且容易理解。由於a~Z對應的ASCII碼值小於256,即創建一個256大小的數組即可,將其中一個字符串對應的字符存入數組中,數組下標為字符對應的ASCII碼值,對應的值為當前字符的個數,然後遍歷另一個字符串對應的字符數組,判斷遍歷得到的字符在整形數組中的值是否為0,若為0則返回false,否則將該字符對應的值減1,遍歷完即得結果。

(3)詳情見下方代碼。希望本文對你有所幫助。

 

算法代碼實現如下:

 

package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 
 * @author liqqc
 *
 */
public class Valid_Anagram {

	// use api method
	public static boolean isAnagram(String s, String t) {
		if (s == null || t == null)
			return false;

		if (s.trim().equals(t.trim()))
			return true;

		if (s.length() != t.length())
			return false;

		char[] charArray = s.toCharArray();
		char[] charArray2 = t.toCharArray();
		Arrays.sort(charArray);
		Arrays.sort(charArray2);

		return new String(charArray).equals(new String(charArray2));
	}

	// use map
	public static boolean isAnagram2(String s, String t) {
		if (s == null || t == null)
			return false;

		if (s.trim().equals(t.trim()))
			return true;

		if (s.length() != t.length())
			return false;

		char[] charArray = s.toCharArray();
		char[] charArray2 = t.toCharArray();

		Map map = new HashMap();
		for (Character c : charArray) {
			if (!map.containsKey(c)) {
				map.put(c, 1);
			} else {
				map.put(c, map.get(c) + 1);
			}
		}

		for (Character c : charArray2) {
			if (!map.containsKey(c)) {
				return false;
			} else {
				if (map.get(c) <= 0) {
					return false;
				} else {
					map.put(c, map.get(c) - 1);
				}
			}
		}

		return true;
	}

	// use array
	public static boolean isAnagram3(String s, String t) {

		if (s == null || t == null)
			return false;

		if (s.length() != t.length())
			return false;

		int[] arr = new int[256];

		for (char c : s.toCharArray()) {
			if (arr[c] == 0) {
				arr[c] = 1;
			} else {
				arr[c] = arr[c] + 1;
			}
		}

		for (char c : t.toCharArray()) {
			if (arr[c] == 0) {
				return false;
			} else {
				arr[c] = arr[c] - 1;
			}
		}

		return true;
	}

}

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved