[Leedcode][JAVA][面试题 16.18][模式匹配][字符串][枚举]

一时失言乱红尘 2023-02-20 02:28 32阅读 0赞

#### 【问题描述】\[中等\] ####

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
    
    示例 1：
    
    输入： pattern = "abba", value = "dogcatcatdog"
    输出： true
    示例 2：
    
    输入： pattern = "abba", value = "dogcatcatfish"
    输出： false
    示例 3：
    
    输入： pattern = "aaaa", value = "dogcatcatdog"
    输出： false
    示例 4：
    
    输入： pattern = "abba", value = "dogdogdogdog"
    输出： true
    解释： "a"="dogdog",b=""，反之也符合规则
    提示：
    
    0 <= len(pattern) <= 1000
    0 <= len(value) <= 1000
    你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

#### 【解答思路】 ####

###### 枚举 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

class Solution { 
        public boolean patternMatching(String pattern, String value) { 
            int count_a = 0, count_b = 0;
            for (char ch: pattern.toCharArray()) { 
                if (ch == 'a') { 
                    ++count_a;
                } else { 
                    ++count_b;
                }
            }
            if (count_a < count_b) { 
                int temp = count_a;
                count_a = count_b;
                count_b = temp;
                char[] array = pattern.toCharArray();
                for (int i = 0; i < array.length; i++) { 
                    array[i] = array[i] == 'a' ? 'b' : 'a';
                }
                pattern = new String(array);
            }
            if (value.length() == 0) { 
                return count_b == 0;
            }
            if (pattern.length() == 0) { 
                return false;
            }
            for (int len_a = 0; count_a * len_a <= value.length(); ++len_a) { 
                int rest = value.length() - count_a * len_a;
                if ((count_b == 0 && rest == 0) || (count_b != 0 && rest % count_b == 0)) { 
                    int len_b = (count_b == 0 ? 0 : rest / count_b);
                    int pos = 0;
                    boolean correct = true;
                    String value_a = "", value_b = "";
                    for (char ch: pattern.toCharArray()) { 
                        if (ch == 'a') { 
                            String sub = value.substring(pos, pos + len_a);
                            if (value_a.length() == 0) { 
                                value_a = sub;
                            } else if (!value_a.equals(sub)) { 
                                correct = false;
                                break;
                            }
                            pos += len_a;
                        } else { 
                            String sub = value.substring(pos, pos + len_b);
                            if (value_b.length() == 0) { 
                                value_b = sub;
                            } else if (!value_b.equals(sub)) { 
                                correct = false;
                                break;
                            }
                            pos += len_b;
                        }
                    }
                    if (correct && !value_a.equals(value_b)) { 
                        return true;
                    }
                }
            }
            return false;
        }
    }

#### 【总结】 ####

###### 1. 有思路要实现 注意细节 Talk is cheap，show me the code. ######

###### 2.双字符串匹配问题 ######

2.1 边界问题 逐个是否为空  
2.2 两个之间的长度 细节比较  
2.3 匹配问题 可以转化为出现次数\*长度  
![在这里插入图片描述][20200622105123664.png]

###### 3.细节 ######

**字符串转字符数组 & 处理 & 字符数组转字符串**

char[] array = pattern.toCharArray();
                for (int i = 0; i < array.length; i++) { 
                    array[i] = array[i] == 'a' ? 'b' : 'a';
                }
                pattern = new String(array);

转载链接：https://leetcode-cn.com/problems/pattern-matching-lcci/solution/mo-shi-pi-pei-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200622104252574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200622104329518.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020062210435338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200622105123664.png]: https://img-blog.csdnimg.cn/20200622105123664.png