编程算法 - 字符串相同 代码(Java)

字符串相同 代码(Java)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 实现一个算法, 确定一个字符串的所有字符是否全都不同. 假使不允许使用额外的数据结构, 又该如何处理.

解法1:

使用数据结构, 设置boolean数组, 把值(value)作为数组的索引(index), 判断数组是否重复.

解法2:

不使用数据结构, 可以通过位(bit)进行判断, 把每个字母映射2进制数的一位, 或运算("|")更新数字的位, 与运算("&")判断是否相同.

代码:

/**
 * @time 2014年7月25日
 */
package array_string;

/**
 * @author C.L.Wang
 *
 */
public class StringCommon {

	public static boolean isUniqueChars(String str) {
		if (str.length() > 256) return false;
		boolean[] char_set = new boolean[256];
		for (int i=0; i<str.length(); i++) {
			int val = str.charAt(i);
			if(char_set[val]) {
				return false;
			}
			char_set[val] = true;
		}
		return true;
	}
	
	public static boolean isUniqueChar2(String str) {
		if (str.length() > 256) return false;
		int checker = 0;
		for (int i=0; i<str.length(); ++i) {
			int val = str.charAt(i);
			if ((checker&(1<<val)) > 0) return false;
			checker |= (1<<val);
		}
		return true;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] words = {"abcde", "hello", "apple", "kite", "padle"};
		for (String word : words) {
			System.out.println(word + ": " + isUniqueChars(word) + " " + isUniqueChar2(word));
		}
		
	}

}

输出:

abcde: true true
hello: false false
apple: false false
kite: true true
padle: true true

编程算法 - 字符串相同 代码(Java),古老的榕树,5-wow.com