题目描述
Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structures?
在不使用额外数据结构的情况下,实现一个算法判断一个字符串中的字符是否都没有重复?
解析:
初看到这道题的时候,脑中第一印象是前不久看过一道类似的题,里面是求出字符串中第一个只出现一次的字符串,翻了一下是剑指offer的第35题,两道题都可以使用hash表的思路。
对于输入的字符串,申请一个256大小的标志位,两道题的思路大致是一致的。
下面给出hashtable的代码:
/* 时间复杂度为O(n) 空间复杂度为O(n) */ bool isUnique( const char *str ) { if ( str == NULL ) return true; const int tableSize = 256; unsigned int hashTable[tableSize]; memset( hashTable, 0, sizeof(hashTable) ); const char *pHashKey = str; while ( *pHashKey != '\0' ) if ( ++hashTable[*pHashKey++] > 1 ) return false; return true; }
上面的代码时间复杂度为O(n),在空间上可以进行优化,因为只要判断该位是否存在,所以可以使用bitmap的方法,此时256个字节,需要8个int来表示,实现代码如下:
#define SetBit(table,index) ( table[index/32] |= (1<<(index%32)) ) #define isBitSet(table,index) ( table[index/32] & (1<<(index%32)) ) bool isUnique2( const char *str ) { if ( str == NULL ) return true; const int tableSize = 256; unsigned int hashTable[tableSize/32]; memset( hashTable, 0, sizeof(hashTable) ); const char *pHashKey = str; while ( *pHashKey != '\0' ) { if ( isBitSet(hashTable, *pHashKey) ) return false; else SetBit(hashTable, *pHashKey); ++pHashKey; } return true; }
到此这道题基本上就结束了。。。。