01.07.md

字符串其它问题

1、第一个只出现一次的字符

题目描述

在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

分析与解法

分析：这道题是2006年google 的一道笔试题。它在今年又出现了，不过换了一种形式。即最近的搜狐笔试大题：数组非常长，如何找到第一个只出现一次的数字，说明算法复杂度。此问题已经在程序员编程艺术系列第二章中有所阐述，在此不再作过多讲解。

代码，可编写如下：

//查找第一个只出现一次的字符，第2个程序
//copyright@ yansha
//July、updated，2011.04.24.
char FirstNotRepeatChar(char* pString)
{
    if (!pString)
        return '\0';

    const int tableSize = 256;
    int hashTable[tableSize] = {0}; //存入数组，并初始化为0

    char* pHashKey = pString;
    while (*(pHashKey) != '\0')
        hashTable[*(pHashKey++)]++;

    while (*pString != '\0')
    {
        if (hashTable[*pString] == 1)
            return *pString;

        pString++;
    }
    return '\0';  //没有找到满足条件的字符，退出
}

2、带通配符的字符串匹配问题

字符串匹配问题：给定一个字符串，按照指定规则对其进行匹配，并将匹配的结果保存至output数组中。多个匹配项用空格间隔，最后一个不需要空格。

要求：

1. 匹配规则中包含通配符?和*，其中?表示匹配任意一个字符，*表示匹配任意多个（>=0）字符。
2. 匹配规则要求匹配最大的字符子串，例如a*d,匹配abbdd而非abbd,即最大匹配子串。
3. 匹配后的输入串不再进行匹配，从当前匹配后的字符串重新匹配其他字符串。

请实现函数：

  char* my_find(char input[], char rule[])

举例说明：

注意事项：

1. 自行实现函数my_find，勿在my_find函数里夹杂输出，且不准用C、C++库，和Java的String对象；
2. 请注意代码的时间，空间复杂度，及可读性，简洁性；
3. input=aaa，rule=aa时，返回一个结果aa，即可。