@TOC

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false

+ (BOOL)hy_isValidParenthesis:(NSString *)s {
    NSMutableArray<NSString *> *stack = [NSMutableArray array];
    
    for (NSInteger i = 0; i < s.length; i++) {
        NSString *ch = [s substringWithRange:NSMakeRange(i, 1)];
        
        if ([ch isEqualToString:@"("] || [ch isEqualToString:@"{"] || [ch isEqualToString:@"["]) {
            // 如果是左括号，则将其推入栈中
            [stack addObject:ch];
        } else {
            // 否则，弹出栈顶元素并检查它是否与当前括号匹配
            NSString *top = stack.lastObject;
            [stack removeLastObject];
            
            if (([ch isEqualToString:@")"] && ![top isEqualToString:@"("]) ||
                ([ch isEqualToString:@"}"] && ![top isEqualToString:@"{"]) ||
                ([ch isEqualToString:@"]"] && ![top isEqualToString:@"["])) {
                return NO;
            }
        }
    }
    
    // 最后，如果栈为空，则说明所有括号都正确闭合
    return stack.count == 0;
}

该算法使用栈来跟踪未关闭的左括号。遍历字符串中的每个字符，如果当前字符是左括号，则将其推入栈中；否则，弹出栈顶元素并检查它是否与当前括号匹配。如果不匹配或栈为空，则说明字符串无效。

最后，如果栈为空，则说明所有括号都正确地闭合了。

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

+ (NSArray<NSString *> *)hy_generateParenthesis:(NSInteger)n {
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    void (^backtrack)(NSString *, NSInteger, NSInteger) = ^(NSString *s, NSInteger left, NSInteger right) {
        if (s.length == n * 2) {
            [result addObject:s];
            return;
        }
        
        if (left < n) {
            // 如果左括号数量小于 n，则可以添加一个左括号
            backtrack([s stringByAppendingString:@"("], left + 1, right);
        }
        
        if (right < left) {
            // 如果右括号数量小于左括号数量，则可以添加一个右括号
            backtrack([s stringByAppendingString:@")"], left, right + 1);
        }
    };
    
    backtrack(@"", 0, 0);
    
    return result;
}

该算法使用回溯方法生成所有可能的括号组合。定义一个辅助函数 backtrack，它维护当前括号字符串 s、已使用的左括号数 left 和已使用的右括号数 right。

如果 s 的长度等于 n 的两倍，则说明我们已经产生了一个有效的括号组合，将其推入结果数组中并返回。否则，我们有两种选择：添加一个左括号或添加一个右括号。

当左括号数量小于 n 时，我们可以添加一个左括号。当右括号数量小于左括号数量时，我们可以添加一个右括号。这两个条件都满足时，我们需要分别尝试添加左括号和右括号。

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

`+ (NSInteger)hy_findSubscripMatchString:(NSString *)haystack needle:(NSString *)needle {
    if (needle.length == 0) {
        return 0;
    }
    
    NSInteger n = needle.length;
    
    // 遍历 haystack 中所有长度为 n 的子串
    for (NSInteger i = 0; i < haystack.length - n + 1; i++) {
        NSString *sub = [haystack substringWithRange:NSMakeRange(i, n)];
        
        if ([sub isEqualToString:needle]) {
            return i;
        }
    }
    
    return -1;
}

该算法使用暴力枚举方法，在 haystack 中逐一查找长度为 n 的子串是否与 needle 相等。如果相等，则返回该子串在 haystack 中的下标。

最后，如果没有找到匹配项，则返回 -1。

要使用该函数，请调用 strStr 方法，并将要查询的字符串作为参数传递给它。它将返回第一个匹配项的下标或 -1。

注释已经尽可能详细地解释了算法的实现过程。此外，我们使用了 NSString 的 substringWithRange: 方法来提取子串。它的语法是 [string substringWithRange:NSMakeRange(location, length)]，其中 location 是起始位置，length 是子串的长度

串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

+ (NSArray<NSNumber *> *)hy_substringConnectsWords:(NSString *)s withWords:(NSArray<NSString *> *)words {
    NSMutableArray<NSNumber *> *res = [NSMutableArray array]; // 用于存储结果
    
    if (!s || !words || words.count == 0) return res; // 特判，若s和words有一个不存在，则返回res
    
    NSInteger wordLen = words[0].length; // 获取单词长度
    NSMutableDictionary<NSString *, NSNumber *> *wordsCount = [NSMutableDictionary dictionary];
    for (NSString *word in words) { // 将words数组中所有字符串存入哈希表，并统计每个字符串出现的次数
        NSNumber *count = wordsCount[word];
        wordsCount[word] = count ? @(count.integerValue + 1) : @1;
    }
    
    for (NSInteger i = 0; i < wordLen; i++) { // 在0到wordLen-1范围内枚举起点
        NSInteger left = i, right = i, count = 0; // 已经匹配的字符串数量
        NSMutableDictionary<NSString *, NSNumber *> *currWordsCount = [NSMutableDictionary dictionary]; // 当前已经匹配的字符串以及它们出现的次数
        
        while (right + wordLen <= s.length) { // 枚举终点
            NSString *word = [s substringWithRange:NSMakeRange(right, wordLen)]; // 获取当前的单词
            right += wordLen; // 更新右指针
            
            NSNumber *wordCount = wordsCount[word];
            if (!wordCount) { // 如果这个单词不在哈希表中，则说明从当前左指针开始没有一个符合要求的子串了，直接跳过
                left = right;
                count = 0; // 此时需要重新统计已经匹配的字符串数量，以及当前已经匹配的字符串以及它们出现的次数
                currWordsCount = [NSMutableDictionary dictionary];
            } else {
                NSNumber *currWordCount = currWordsCount[word];
                currWordsCount[word] = currWordCount ? @(currWordCount.integerValue + 1) : @1; // 将当前单词存入哈希表中，并更新它的出现次数
                
                while (currWordsCount[word].integerValue > wordCount.integerValue) { // 如果当前单词的出现次数大于哈希表中该单词的出现次数，则说明当前的子串不符合要求，需要将左指针右移
                    NSString *removeWord = [s substringWithRange:NSMakeRange(left, wordLen)];
                    left += wordLen;
                    currWordsCount[removeWord] = @(currWordsCount[removeWord].integerValue - 1);
                    count--; // 更新统计值
                }
                
                count++; // 已经匹配的字符串数量加1
                
                if (count == words.count) { // 如果已经匹配的字符串数量等于words数组的长度，则说明找到了一个符合要求的子串，记录下其起始位置
                    [res addObject:@(left)];
                    NSString *removeWord = [s substringWithRange:NSMakeRange(left, wordLen)];
                    left += wordLen;
                    currWordsCount[removeWord] = @(currWordsCount[removeWord].integerValue - 1);
                    count--;
                }
            }
        }
    }
    
    return res; // 返回结果数组
}

主要思路是：遍历s字符串，依次截取长度为words数组中所有单词长度之和的子串，判断该子串是否由words数组中所有单词组成。具体步骤：

1、根据words[0]的长度计算出每个单词的长度；
2、计算所有单词组成的子串长度subStringLength；
3、将words数组转换成字典wordCounts，key是单词，value是该单词出现的次数（因为可以重复）；
4.遍历s字符串，依次截取长度为subStringLength的子串，判断该子串是否符合条件；
5、对于每个子串，将其按照单词的长度拆分成多个单词，判断这些单词是否可以组成words数组中所有单词的组合；
6、如果符合条件，将该子串的起始位置添加到结果数组中。

时间复杂度为O(n^2)，空间复杂度为O(n)，其中n为s字符串的长度。

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0

+ (NSInteger)hy_longestValidParentheses:(NSString *)s {
    // 用栈来保存左括号的下标
    NSMutableArray<NSNumber *> *stack = [NSMutableArray arrayWithObject:@(-1)];
    NSInteger maxLength = 0;

    for (NSInteger i = 0; i < s.length; i++) {
        NSString *c = [s substringWithRange:NSMakeRange(i, 1)];
        if ([c isEqualToString:@"("]) {
            // 如果当前字符是左括号，则将其下标入栈
            [stack addObject:@(i)];
        } else {
            // 如果当前字符是右括号，则将栈顶元素弹出
            [stack removeLastObject];
            if (stack.count == 0) {
                // 如果栈为空，说明没有左括号与该右括号匹配，则将该右括号的下标入栈作为新的起点
                [stack addObject:@(i)];
            } else {
                // 如果栈不为空，则计算以当前右括号结尾的最长有效括号子串长度
                NSInteger length = i - stack.lastObject.integerValue;
                maxLength = MAX(maxLength, length);
            }
        }
    }

    return maxLength;
}

主要思路是：使用栈来判断是否有有效的括号匹配。具体步骤：
将-1压入栈底，在后面计算长度时可以方便地得到以第一个左括号开头的子串长度；
遍历字符串s，如果当前字符是左括号，则将其下标入栈；
如果当前字符是右括号，则将栈顶元素弹出，如果栈为空，说明没有左括号与该右括号匹配，则将该右括号的下标入栈作为新的起点；
如果栈不为空，则计算以当前右括号结尾的最长有效括号子串长度，即当前右括号下标减去栈顶元素下标，取这些长度的最大值；
返回最大长度。
时间复杂度为O(n)，空间复杂度为O(n)，其中n为s字符串的长度。

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

+ (NSString *)hy_multiply:(NSString *)num1 with:(NSString *)num2 {
    // 处理特殊情况
    if ([num1 isEqualToString:@"0"] || [num2 isEqualToString:@"0"]) {
        return @"0";
    }

    // 将num1和num2翻转，并转换成整数数组，方便计算
    NSMutableArray<NSNumber *> *num1Arr = [NSMutableArray array];
    for (NSInteger i = num1.length - 1; i >= 0; i--) {
        NSString *digitStr = [num1 substringWithRange:NSMakeRange(i, 1)];
        [num1Arr addObject:@(digitStr.integerValue)];
    }
    NSMutableArray<NSNumber *> *num2Arr = [NSMutableArray array];
    for (NSInteger i = num2.length - 1; i >= 0; i--) {
        NSString *digitStr = [num2 substringWithRange:NSMakeRange(i, 1)];
        [num2Arr addObject:@(digitStr.integerValue)];
    }

    // 计算乘积并保存到result数组中
    NSMutableArray<NSNumber *> *result = [NSMutableArray arrayWithCapacity:num1Arr.count + num2Arr.count];
    for (NSInteger i = 0; i < num1Arr.count + num2Arr.count; i++) {
        [result addObject:@(0)];
    }
    for (NSInteger i = 0; i < num1Arr.count; i++) {
        for (NSInteger j = 0; j < num2Arr.count; j++) {
            NSInteger product = num1Arr[i].integerValue * num2Arr[j].integerValue;
            NSInteger sum = result[i+j].integerValue + product % 10;
            NSInteger carry = sum / 10;
            NSInteger digit = sum % 10;
            
            // 将NSNumber对象转换成可变类型，修改其值，再重新封装成NSNumber对象
            NSMutableArray<NSNumber *> *mutableResult = [NSMutableArray arrayWithArray:result];
            mutableResult[i+j] = @(digit);
            mutableResult[i+j+1] = @(mutableResult[i+j+1].integerValue + carry + product / 10);
            result = [NSMutableArray arrayWithArray:mutableResult];
        }
    }

    // 对result数组进行进位处理
    for (NSInteger i = 0; i < result.count - 1; i++) {
        NSInteger carry = [result[i] integerValue] / 10;
        result[i] = @([result[i] integerValue] % 10);
        
        // 同上，将NSNumber对象转换成可变类型，修改其值，再重新封装成NSNumber对象
        NSMutableArray<NSNumber *> *mutableResult = [NSMutableArray arrayWithArray:result];
        mutableResult[i+1] = @(mutableResult[i+1].integerValue + carry);
        result = [NSMutableArray arrayWithArray:mutableResult];
    }

    // 将result数组翻转并去掉前导0，将数组转换成字符串返回
    while (result.count > 1 && result.lastObject.integerValue == 0) {
        [result removeLastObject];
    }
    NSMutableString *resultStr = [NSMutableString string];
    for (NSInteger i = result.count - 1; i >= 0; i--) {
        [resultStr appendFormat:@"%ld", result[i].integerValue];
    }
    return resultStr;
}

主要思路:
从低位到高位逐位相乘，将结果保存到一个数组中，再对数组进行进位处理。具体步骤：
处理特殊情况，如果有一个字符串为0，则直接返回"0"；
将num1和num2翻转，并转换成整数数组，方便计算；
创建一个长度为len(num1)+len(num2)的数组result，用于保存乘积；
从低位到高位逐位相乘，将结果保存到result数组中；
对result数组进行进位处理，具体方法是：对于result[i]，将其除以10得到进位carry，将result[i]对10取模得到当前位的值，将carry加到result[i+1]中；
将result数组翻转并去掉前导0，将数组转换成字符串返回。
时间复杂度为O(n^2)，其中n为num1和num2中较长的那个字符串的长度。对于每一位的乘积都需要计算一次，并且需要进行进位处理。空间复杂度为O(n)。

最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0

+ (NSInteger)hy_threeSumClosest:(NSArray<NSNumber *> *)nums target:(NSInteger)target {
    // 对数组进行排序
    NSArray<NSNumber *> *sortedNums = [nums sortedArrayUsingSelector:@selector(compare:)];
    
    NSInteger closestSum = sortedNums[0].integerValue + sortedNums[1].integerValue + sortedNums[2].integerValue;
    
    for (NSInteger i = 0; i < sortedNums.count - 2; i++) {
        NSInteger left = i + 1;
        NSInteger right = sortedNums.count - 1;
        
        while (left < right) {
            NSInteger sum = sortedNums[i].integerValue + sortedNums[left].integerValue + sortedNums[right].integerValue;
            
            // 如果新的和更接近目标值，则更新结果
            if (labs(target - sum) < labs(target - closestSum)) {
                closestSum = sum;
            }
            
            // 根据当前和与目标值的大小关系移动指针
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return sum;
            }
        }
    }
    
    return closestSum;
}

该算法首先对数组进行排序。然后，遍历排序后的数组并选择一个数字作为三元组中的第一个数字。接下来，使用双指针算法在剩余的数字中查找两个数字，使它们的和等于目标值（即 target 减去当前数字）。

如果当前和与目标值的差比当前最接近的和与目标值的差更小，则更新结果。最后返回最接近目标值的三数之和。

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

以下是 Objective-C 代码，用于查找三数之和为 0 的唯一三元组：

+ (NSArray<NSArray<NSNumber *> *> *)hy_threeSum:(NSArray<NSNumber *> *)nums {
    NSMutableArray<NSArray<NSNumber *> *> *result = [NSMutableArray array];
    
    if (nums.count < 3) {
        return result;
    }
    
    // 对数组进行排序
    NSArray<NSNumber *> *sortedNums = [nums sortedArrayUsingSelector:@selector(compare:)];
    
    for (NSInteger i = 0; i < sortedNums.count - 2; i++) {
        // 如果当前数字与上一个数字相同，则跳过以避免重复结果
        if (i > 0 && [sortedNums[i] isEqualToNumber:sortedNums[i - 1]]) {
            continue;
        }
        
        NSInteger left = i + 1;
        NSInteger right = sortedNums.count - 1;
        
        while (left < right) {
            NSInteger sum = sortedNums[i].integerValue + sortedNums[left].integerValue + sortedNums[right].integerValue;
            
            if (sum == 0) {
                [result addObject:@[sortedNums[i], sortedNums[left], sortedNums[right]]];
                
                // 跳过重复的数字
                while (left < right && [sortedNums[left] isEqualToNumber:sortedNums[left + 1]]) {
                    left++;
                }
                
                while (left < right && [sortedNums[right] isEqualToNumber:sortedNums[right - 1]]) {
                    right--;
                }
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

该算法首先对数组进行排序，然后遍历排序后的数组并选择一个数字作为三元组中的第一个数字。接下来，使用双指针算法在剩余的数字中查找两个数字，使它们的和等于目标值（即当前数字的相反数）。

由于答案不能包含重复的三元组，因此我们需要跳过具有相同值的数字。这可以通过检查左右指针所在位置的前一个或后一个数字来实现。

回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

+ (BOOL)hy_isPalindrome:(NSInteger)x {
    // 如果x小于0或者最后一位是0且x不等于0，则不是回文数
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return NO;
    }
    
    NSInteger reversed = 0;
    while (x > reversed) {
        // 取出最后一位数字
        NSInteger digit = x % 10;
        // 将该位数字加入反转后的结果中
        reversed = reversed * 10 + digit;
        // 去掉已经处理过的数字
        x /= 10;
    }
    
    // 如果x有奇数位，则reversed比x多一位，需要去掉中间的那一位
    return x == reversed || x == reversed / 10;
}

注解：

• isPalindrome: 是该方法的名称，输入参数为一个 NSInteger 类型的整数，输出也是一个 BOOL 类型的值。
• i如果给定整数小于 0 或者最后一位是 0 且整数不为 0，则肯定不是回文数，直接返回 NO。
• i初始化反转后的结果为 0。
• i循环取出给定整数的最后一位数字，并将其加入反转后的结果中。
• i在每次循环中判断反转后的结果是否超过了给定整数的一半长度，如果超过了，则说明已经处理完了一半位数，可以开始比较了。
• i如果给定整数有奇数位，则反转后的结果比给定整数多一位，需要去掉中间的那一位，然后比较是否相等。
• i最后返回比较结果。

该算法的时间复杂度为 O(log n)，空间复杂度为 O(1)。

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

+ (NSString *)longestCommonPrefix:(NSArray<NSString *> *)strs {
    if (strs == nil || strs.count == 0) { // 如果输入数组为空，则返回空字符串
        return @"";
    }
    
    NSUInteger minLength = NSUIntegerMax;
    for (NSString *s in strs) { // 先找出所有字符串中长度最短的那个
        minLength = MIN(minLength, s.length);
    }
    
    NSMutableString *prefix = [NSMutableString stringWithCapacity:minLength];
    for (NSUInteger i = 0; i < minLength; i++) {
        unichar c = [strs[0] characterAtIndex:i]; // 取出第一个字符串的第i个字符
        for (NSUInteger j = 1; j < strs.count; j++) { // 遍历剩余的字符串，判断是否都包含该字符
            NSString *s = strs[j];
            if ([s characterAtIndex:i] != c) { // 如果遇到不同的字符，则返回当前已经匹配的前缀
                return prefix;
            }
        }
        [prefix appendFormat:@"%C", c]; // 如果所有字符串中都包含该字符，则将其加入结果中
    }
    
    return prefix;
}

注解：
longestCommonPrefix 是该函数的名称，输入参数为一个字符串数组，输出也是一个字符串。
如果输入数组为空，则直接返回空字符串。
先找出所有字符串中长度最短的那个。
创建一个空字符串用于存储公共前缀，然后循环遍历所有字符串中的每个字符，判断它们是否都相同，如果是，则将该字符加入到结果字符串中；否则，直接返回当前已经匹配的前缀。
最后返回结果字符串。

这种方法的时间复杂度为 O(nm)，其中 n 是字符串数组的长度，m 是所有字符串中的字符数的最小值。

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0

+ (NSInteger)hy_reverseInteger:(NSInteger)x {
    NSInteger result = 0;
    while (x != 0) {
        // 取出最后一位数字
        NSInteger digit = x % 10;
        // 判断是否会溢出
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
            return 0;
        }
        if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) {
            return 0;
        }
        // 将该位数字加入结果中
        result = result * 10 + digit;
        // 去掉已经处理过的数字
        x /= 10;
    }
    return result;
}

注解：

• reverseInteger: 是该方法的名称，输入参数为一个 NSInteger 类型的整数，输出也是一个 NSInteger 类型的整数。
• 初始化结果为 0。
• 循环取出给定整数的最后一位数字，并将其加入结果中。
• 在每次循环中判断是否会溢出，如果超过了 32 位整数的范围，则返回 0。
• 返回结果。
  该算法的时间复杂度为 O(log n)，空间复杂度为 O(1)。

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"

+ (NSString *)hy_longestPalindrome:(NSString *)s {
    NSInteger length = s.length;
    if (length < 2) {
        return s;
    }
    
    NSInteger start = 0;
    NSInteger maxLength = 1;
    for (NSInteger i = 0; i < length; i++) {
        // 寻找以i为中心的奇数长度的回文串
        NSInteger left = i - 1;
        NSInteger right = i + 1;
        while (left >= 0 && right < length && [s characterAtIndex:left] == [s characterAtIndex:right]) {
            left--;
            right++;
        }
        NSInteger oddLength = right - left - 1;
        
        // 寻找以i和i+1为中心的偶数长度的回文串
        left = i;
        right = i + 1;
        while (left >= 0 && right < length && [s characterAtIndex:left] == [s characterAtIndex:right]) {
            left--;
            right++;
        }
        NSInteger evenLength = right - left - 1;
        
        // 取最长的回文串
        NSInteger currentMaxLength = MAX(oddLength, evenLength);
        if (currentMaxLength > maxLength) {
            maxLength = currentMaxLength;
            start = i - (maxLength - 1) / 2;
        }
    }
    
    NSRange range = NSMakeRange(start, maxLength);
    NSString *result = [s substringWithRange:range];
    return result;
}

longestPalindrome: 是该方法的名称，输入参数为一个 NSString 对象，输出也是一个 NSString 对象。
首先判断字符串长度是否小于 2，如果是，则直接返回原字符串。
初始化最长回文子串的起始位置为 0，长度为 1。
遍历字符串中每个字符，以该字符为中心分别向左右扩展，寻找奇数长度和偶数长度的回文串，并记录其长度。
取两种回文串中长度较大的一个，判断是否比当前最长回文子串的长度更长，如果是，则更新最长回文子串的起始位置和长度。
最后利用 substringWithRange 函数获取最长回文子串，并返回。

通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配： '?' 可以匹配任何单个字符。
'*' 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

- (BOOL)hy_isMatch:(NSString *)s pattern:(NSString *)p {
    NSInteger m = s.length;
    NSInteger n = p.length;
    
    // 创建一个二维数组 dp，用于存储中间结果
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:m + 1];
    for (NSInteger i = 0; i <= m; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:n + 1];
        
        for (NSInteger j = 0; j <= n; j++) {
            [row addObject:@NO];
        }
        
        [dp addObject:row];
    }
    
    // 空字符串和空模式匹配
    dp[0][0] = @YES;
    
    // 处理第一行，即空字符串与非空模式
    for (NSInteger j = 1; j <= n; j++) {
        if ([p characterAtIndex:j - 1] == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }
    
    // 处理其余子问题
    for (NSInteger i = 1; i <= m; i++) {
        for (NSInteger j = 1; j <= n; j++) {
            unichar sc = [s characterAtIndex:i - 1];
            unichar pc = [p characterAtIndex:j - 1];
            
            // 如果当前模式字符是通配符，则可以使用前面的结果
            if (pc == '*') {
                dp[i][j] = [NSNumber numberWithBool:(dp[i - 1][j].boolValue || dp[i][j - 1].boolValue)];

            } else if (pc == '?' || sc == pc) { // 如果当前字符匹配，则可以使用前面的结果
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    
    return [[dp lastObject] lastObject].boolValue;
}

该算法使用动态规划方法实现通配符匹配。我们首先创建一个二维数组 dp，用于存储中间结果。然后，我们将空字符串和空模式设置为匹配，并处理第一行，即空字符串与非空模式。
接下来，我们处理其余子问题。对于每个字符和模式字符组合，我们检查以下三种情况：

• 如果当前模式字符是通配符，则可以使用前面的结果。
• 如果当前字符匹配，则可以使用前面的结果。
• 否则，当前字符和模式字符无法匹配，因此不能使用前面的结果。
• 最终，我们返回 dp[m][n]，其中 m 是输入字符串的长度，n 是字符模式的长度。

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

+ (NSInteger)hy_strStr:(NSString *)haystack needle:(NSString *)needle {
    // 如果 needle 为空，则返回 0
    if (needle.length == 0) {
        return 0;
    }
    
    // 如果 haystack 长度小于 needle 长度，则直接返回 -1
    if (haystack.length < needle.length) {
        return -1;
    }
    
    NSInteger n = haystack.length;
    NSInteger m = needle.length;
    
    // 在 haystack 中滑动窗口，并比较每个子串是否等于 needle
    for (NSInteger i = 0; i <= n - m; i++) {
        NSString *substring = [haystack substringWithRange:NSMakeRange(i, m)];
        
        if ([substring isEqualToString:needle]) {
            return i;
        }
    }
    
    // 如果找不到匹配项，则返回 -1
    return -1;
}

该算法使用滑动窗口方法，在输入字符串 haystack 中查找字符串 needle 的第一个匹配项的下标。

我们首先检查 needle 是否为空。如果为空，则 haystack 中的任何位置都是匹配项，因此我们返回 0。

然后，我们检查 haystack 的长度是否小于 needle 的长度。如果是，则 needle 没有可能成为 haystack 的子字符串，因此我们直接返回 -1。

接下来，我们使用滑动窗口方法在 haystack 中遍历每个子字符串，并比较其是否与 needle 相等。如果找到匹配项，则返回其下标。

如果遍历完 haystack 中的所有子字符串，仍然找不到匹配项，则返回 -1。

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

[图片上传失败...(image-20567e-1683713324737)]

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]

+ (NSArray<NSString *> *)hy_letterCombinations:(NSString *)digits {
    // 创建字典，用于存储数字到字母的映射关系
    NSDictionary *keypad = @{
        @"2": @"abc",
        @"3": @"def",
        @"4": @"ghi",
        @"5": @"jkl",
        @"6": @"mno",
        @"7": @"pqrs",
        @"8": @"tuv",
        @"9": @"wxyz"
    };
    
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    // 如果输入字符串为空，则直接返回空数组
    if (digits.length == 0) {
        return result;
    }
    
    // 初始化结果字符串和数字字符索引列表
    NSMutableString *current = [NSMutableString string];
    NSMutableArray<NSNumber *> *indices = [NSMutableArray arrayWithCapacity:digits.length];
    for (NSInteger i = 0; i < digits.length; i++) {
        [indices addObject:@(0)];
    }

    NSInteger pos = 0;
    
    while (pos >= 0) {
        NSString *digit = [digits substringWithRange:NSMakeRange(pos, 1)];
        NSString *letters = [keypad objectForKey:digit];
        NSInteger index = [[indices objectAtIndex:pos] integerValue];
        
        // 如果当前位置已经到达该数字对应的字母末尾，则回溯到前一个数字
        if (index == letters.length) {
            pos--;
            continue;
        }
        
        // 否则，将当前位置的字母添加到结果字符串中，并更新数字字符索引列表
        unichar letter = [letters characterAtIndex:index];
        [current appendFormat:@"%c", letter];
        [indices replaceObjectAtIndex:pos withObject:@(index + 1)];
        
        // 如果已经处理完最后一个数字，则将结果字符串添加到结果列表中，并回溯到前一个数字
        if (pos == digits.length - 1) {
            [result addObject:[NSString stringWithString:current]];
            pos--;
        } else {
            // 否则，继续处理下一个数字
            pos++;
            [indices replaceObjectAtIndex:pos withObject:@(0)];
        }
    }
    
    return result;
}

该算法使用回溯方法来生成所有可能的字母组合。我们首先创建一个字典，用于存储数字到字母的映射关系。然后，我们初始化一个空数组作为结果列表，并检查输入字符串是否为空。如果输入字符串为空，则直接返回空数组。
在主循环中，我们从左到右遍历数字字符，并使用数字到字母映射字典获取对应的字母集合。我们使用一个数字字符索引列表来跟踪每个数字字符当前使用的字母位置。
如果当前数字字符已经在其字母集合的末尾，则回溯到前一个数字字符，并继续寻找可用的字母。否则，我们将当前字母添加到结果字符串中，并更新数字字符索引列表。
如果已经处理了最后一个数字字符，则将结果字符串添加到结果列表中，并回溯到前一个数字字符。否则，我们继续处理下一个数字字符，并将其对应的字母作为结果字符串的下一个字符。

最终，我们返回生成的所有结果字符串作为字母组合的列表。

罗马数字转整数

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3
示例 2:

输入: s = "IV"
输出: 4
示例 3:

输入: s = "IX"
输出: 9
示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

+ (NSInteger)hy_romanToInt:(NSString *)s {
    // 创建字典，用于存储罗马数字符号和对应的阿拉伯数字值
    NSDictionary *romanValues = @{@"I": @1, @"V": @5, @"X": @10, @"L": @50, @"C": @100, @"D": @500, @"M": @1000};
    
    NSInteger result = 0;
    NSInteger prevValue = 0;
    
    // 从右到左遍历罗马数字字符
    for (NSInteger i = s.length - 1; i >= 0; i--) {
        NSString *symbol = [s substringWithRange:NSMakeRange(i, 1)];
        NSInteger value = [[romanValues objectForKey:symbol] integerValue];
        
        // 如果当前值小于前一个值，则减去当前值；否则加上当前值
        if (value < prevValue) {
            result -= value;
        } else {
            result += value;
        }
        
        prevValue = value;
    }
    
    return result;
}

该算法使用字典来存储罗马数字符号和对应的阿拉伯数字值。然后，我们从右到左遍历罗马数字字符，并计算每个字符的值。

如果当前字符的值小于前一个字符的值，则意味着需要减去当前值。例如，在 IV 中，第一个字符 I 的值为 1，而第二个字符 V 的值为 5。由于 I 在 V 的左边，所以我们需要在 V 的值中减去 I 的值，得到 4。

如果当前字符的值大于或等于前一个字符的值，则需要将该值添加到结果中。例如，在 IX 中，第一个字符 I 的值为 1，而第二个字符 X 的值为 10。由于 I 在 X 的左边，所以我们需要在 X 的值中加上 I 的值，得到 9。

最终，我们返回计算出的整数值。

整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

示例 1:
输入: num = 3
输出: "III"

示例 2:
输入: num = 4
输出: "IV"

示例 3:
输入: num = 9
输出: "IX"

示例 4:
输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:
输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

+ (NSString *)hy_intToRoman:(NSInteger)num {
    // 创建两个数组，分别存储罗马数字和对应的阿拉伯数字值
    NSArray *romanValues = @[@1000, @900, @500, @400, @100, @90, @50, @40, @10, @9, @5, @4, @1];
    NSArray *romanSymbols = @[@"M", @"CM", @"D", @"CD", @"C", @"XC", @"L", @"XL", @"X", @"IX", @"V", @"IV", @"I"];
    
    NSMutableString *result = [NSMutableString string];
    
    // 从高位到低位遍历每个阿拉伯数字值
    for (NSInteger i = 0; i < romanValues.count && num > 0; i++) {
        NSInteger value = [[romanValues objectAtIndex:i] integerValue];
        NSString *symbol = [romanSymbols objectAtIndex:i];
        
        // 计算当前罗马数字可以重复的次数
        NSInteger numSymbols = num / value;
        
        // 将当前罗马数字添加到结果字符串中，并减去相应的值
        for (NSInteger j = 0; j < numSymbols; j++) {
            [result appendString:symbol];
        }
        
        num -= value * numSymbols;
    }
    
    return result;
}

该算法使用贪心策略来将整数转换为罗马数字。我们首先创建两个数组，一个包含罗马数字的符号，另一个包含罗马数字的值。然后，我们按递减顺序遍历这两个数组中的元素，直到整数值为零。
在每次迭代中，我们计算当前罗马数字可以重复的次数，并将其添加到结果字符串中。同时，我们从整数值中减去相应的阿拉伯数字值。

最终，我们返回结果字符串作为罗马数字的表示形式。

字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
第 3 步："42"（读入 "42"）
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：
输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
第 3 步："   -42"（读入 "42"）
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

示例代码

+ (int)hy_myAtoi:(NSString *)s {
    if (!s || s.length == 0) {
        return 0;
    }
    
    NSInteger i = 0;
    NSInteger sign = 1;
    NSInteger result = 0;
    
    // 移除前导空格
    while (i < s.length && [s characterAtIndex:i] == ' ') {
        i++;
    }
    
    // 处理正负号
    if (i < s.length && ([s characterAtIndex:i] == '+' || [s characterAtIndex:i] == '-')) {
        sign = [s characterAtIndex:i] == '-' ? -1 : 1;
        i++;
    }
    
    // 处理数字字符
    while (i < s.length && [s characterAtIndex:i] >= '0' && [s characterAtIndex:i] <= '9') {
        int digit = [s characterAtIndex:i] - '0';
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) {
            return sign == -1 ? INT_MIN : INT_MAX;
        }
        result = result * 10 + digit;
        i++;
    }
    
    return (int)(sign * result);
}

该算法首先移除前导空格，并处理正负号。然后它逐个字符地读取数字字符，并将其转换为整数。如果整数超出了 32 位有符号整数范围，则会截断该整数以使其保持在此范围内。
要使用该函数，请调用 myAtoi 方法，并将要转换的字符串作为参数传递给它。

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例代码

- (NSInteger)hy_lengthOfLongestSubstring:(NSString *)s {
    if (s.length == 0) {
        return 0;
    }
    
    NSInteger maxLength = 0;
    NSInteger left = 0, right = 0;
    NSMutableDictionary *charDict = [NSMutableDictionary dictionary];
    
    while (right < s.length) {
        NSString *currentChar = [s substringWithRange:NSMakeRange(right, 1)];
        if ([charDict objectForKey:currentChar]) {
            NSNumber *prevIndex = [charDict objectForKey:currentChar];
            left = MAX(left, prevIndex.integerValue + 1);
        }
        
        [charDict setObject:@(right) forKey:currentChar];
        maxLength = MAX(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
}

这个算法的基本思想是使用滑动窗口来维护最长不重复子串。我们使用两个指针 left 和 right 来表示当前窗口的左右边界。我们还使用一个字典来存储每个字符在字符串中出现的最后位置（即上一次出现的位置）。
当我们移动 right 指针时，我们检查当前字符是否已经在窗口中出现。如果是，则更新 left 指针以跳过前面的所有重复字符，并且将当前字符的位置添加到字典中。同时，我们还需要更新最长不重复子串的长度。
要找到字符串中的最长不重复子串长度，只需调用 lengthOfLongestSubstring 方法，并将要计算的字符串作为参数传递给它即可。

正则表达式匹配-提取字符串中的数字

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

Code

+ (BOOL)hy_isMatch:(NSString *)s withPattern:(NSString *)p {
    if (!p || p.length == 0) {
        return !s || s.length == 0;
    }
    
    BOOL firstMatch = s && s.length > 0 && ([p characterAtIndex:0] == [s characterAtIndex:0] || [p characterAtIndex:0] == '.');
    
    if (p.length >= 2 && [p characterAtIndex:1] == '*') {
        return [self hy_isMatch:s withPattern:[p substringFromIndex:2]] || (firstMatch && [self hy_isMatch:[s substringFromIndex:1] withPattern:p]);
    } else {
        return firstMatch && [self hy_isMatch:[s substringFromIndex:1] withPattern:[p substringFromIndex:1]];
    }
}

该算法使用递归来实现正则表达式匹配。它首先检查字符规律是否为空。如果是，则返回 true 如果要匹配的字符串为空；否则，如果要匹配的字符串不为空，则返回 false。
然后，算法检查模式的第一个字符是否与字符串的第一个字符匹配。如果相匹配，则算法将继续对剩余的字符串和模式进行匹配。如果模式的下一个字符是 '*'，则算法可以选择跳过该字符或重复前一个字符，并在两种情况下继续递归搜索。
最后，如果整个字符串都已匹配，并且整个模式也已处理完毕，则返回 true；否则，如果字符串没有全部匹配或者模式仍然存在未处理的字符，则返回 false。

有效数字

有效数字（按顺序）可以分成以下几个部分：
一个 小数 或者 整数
（可选）一个 'e' 或 'E' ，后面跟着一个 整数
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
至少一位数字
部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

示例 1：

输入：s = "0"
输出：true
示例 2：

输入：s = "e"
输出：false
示例 3：

输入：s = "."
输出：false

typedef NS_ENUM(NSInteger, HYNumberState) {
    STATE_INITIAL,              // 初始状态
    STATE_INT_SIGN,             // 整数符号状态
    STATE_INTEGER,              // 整数状态
    STATE_POINT,                // 小数点状态
    STATE_POINT_WITHOUT_INT,    // 前面无整数小数点状态
    STATE_FRACTION,             // 小数状态
    STATE_EXP,                  // 指数字符状态
    STATE_EXP_SIGN,             // 指数符号状态
    STATE_EXP_NUMBER,           // 指数数字状态
    STATE_END                   // 结束状态
};

typedef NS_ENUM(NSInteger, HYNumberCharType) {
    CHAR_NUMBER,                // 数字类型
    CHAR_EXP,                   // 指数字符类型
    CHAR_POINT,                 // 小数点类型
    CHAR_SIGN,                  // 符号类型
    CHAR_ILLEGAL                // 非法字符类型
};


+ (BOOL)hy_isNumber:(NSString *)s {
    // 定义状态转移规则字典
       NSDictionary *stateMap = @{
           @(STATE_INITIAL): @{
               @(CHAR_NUMBER): @(STATE_INTEGER),
               @(CHAR_POINT): @(STATE_POINT_WITHOUT_INT),
               @(CHAR_SIGN): @(STATE_INT_SIGN)
           },
           @(STATE_INT_SIGN): @{
               @(CHAR_NUMBER): @(STATE_INTEGER),
               @(CHAR_POINT): @(STATE_POINT_WITHOUT_INT)
           },
           @(STATE_INTEGER): @{
               @(CHAR_NUMBER): @(STATE_INTEGER),
               @(CHAR_EXP): @(STATE_EXP),
               @(CHAR_POINT): @(STATE_POINT)
           },
           @(STATE_POINT): @{
               @(CHAR_NUMBER): @(STATE_FRACTION),
               @(CHAR_EXP): @(STATE_EXP)
           },
           @(STATE_POINT_WITHOUT_INT): @{
               @(CHAR_NUMBER): @(STATE_FRACTION)
           },
           @(STATE_FRACTION): @{
               @(CHAR_NUMBER): @(STATE_FRACTION),
               @(CHAR_EXP): @(STATE_EXP)
           },
           @(STATE_EXP): @{
               @(CHAR_NUMBER): @(STATE_EXP_NUMBER),
               @(CHAR_SIGN): @(STATE_EXP_SIGN)
           },
           @(STATE_EXP_SIGN): @{
               @(CHAR_NUMBER): @(STATE_EXP_NUMBER)
           },
           @(STATE_EXP_NUMBER): @{
               @(CHAR_NUMBER): @(STATE_EXP_NUMBER)
           }
       };
       
    HYNumberState state = STATE_INITIAL;            // 初始状态为 STATE_INITIAL
    NSUInteger length = [s length];         // 输入字符串的长度
       
    for (NSUInteger i = 0; i < length; i++) {
        HYNumberCharType type = [self toCharType:[s characterAtIndex:i]];   // 将当前字符转换成字符类型
        if (![stateMap[@(state)] objectForKey:@(type)]) {          // 如果当前状态不能接受该类型的字符
            return NO;                                              // 直接返回 NO，说明输入的字符串不是一个有效数字
        } else {
            state = [[stateMap[@(state)] objectForKey:@(type)] integerValue];   // 根据状态转移规则将状态转移到下一个状态
        }
    }
    
    return state == STATE_INTEGER || state == STATE_POINT || state == STATE_FRACTION || state == STATE_EXP_NUMBER || state == STATE_END;  // 最终状态必须为有效数字的结束状态之一
}

+(HYNumberCharType)toCharType:(unichar)ch {
    if (ch >= '0' && ch <= '9') {           // 如果当前字符是数字
        return CHAR_NUMBER;
    } else if (ch == 'e' || ch == 'E') {    // 如果当前字符是指数字符
        return CHAR_EXP;
    } else if (ch == '.') {                 // 如果当前字符是小数点
        return CHAR_POINT;
    } else if (ch == '+' || ch == '-') {   // 如果当前字符是符号
        return CHAR_SIGN;
    } else {
        return CHAR_ILLEGAL;                // 否则为非法字符类型
    }
}

该实现首先定义了一个有限状态机，其中每个状态都是一个对象，其属性表示在该状态下接受的字符类型以及转移后的状态。具体而言，有以下几种字符类型：空格、符号（+/-）、数字、小数点、e/E和无效字符。其中，状态0表示起始状态，在该状态下可以接受的字符类型有空格、符号、数字和小数点；状态3、4、5、8和9分别表示不同的有效数字结束状态，如果最终状态为这些状态之一，则说明输入的字符串是一个有效数字。

接下来，使用一个循环遍历输入字符串中的每个字符。在循环体中，首先判断当前字符属于哪种类型；然后，查找当前状态能否接受该类型的字符，如果不能，则说明输入的字符串不是一个有效数字，可以直接返回false；否则，将状态转移为下一个状态。最后，检查最终状态是否为有效数字的结束状态之一，如果是，则返回true，否则返回false。