LeetCode //C - 290. Word Pattern

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 290. Word Pattern。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
 

Example 1:

Input: pattern = “abba”, s = “dog cat cat dog”
Output: true

Example 2:

Input: pattern = “abba”, s = “dog cat cat fish”
Output: false

Example 3:

Input: pattern = “aaaa”, s = “dog cat cat dog”
Output: false

Constraints:
  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lowercase English letters and spaces ’ '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.

From: LeetCode
Link: 290. Word Pattern


Solution:

Ideas:

The code for the wordPattern function is designed to determine whether a given string s follows a specific pattern. Here’s a breakdown of the idea behind the code:

  1. Initialization: The code initializes an array of pointers words, where each index corresponds to a lowercase letter in the pattern (from ‘a’ to ‘z’). This array will be used to track the mapping between each character in the pattern and a corresponding word in the string s.

  2. String Copy: Since the code utilizes strtok to tokenize the string s, which alters the original string, a copy of the string is made to preserve the input.

  3. Tokenization and Mapping: The code tokenizes the string s into words and iterates through these words alongside the characters in the pattern:

  • If the pattern is exhausted before all words are processed, the function returns false, as there is a mismatch in length.
  • For each character in the pattern, the code checks whether it has been mapped to a word before. If not, it verifies that no other character has been mapped to the current word (to ensure a bijection). If all is well, the current character is mapped to the current word.
  • If the character has already been mapped to a word, the code checks that this word matches the current word in the string. If there’s a mismatch, the function returns false.
  1. Length Check: After processing all words, the code checks whether the pattern’s length matches the number of words. If there’s a mismatch, the function returns false.

  2. Result: If all checks pass, the function returns true, indicating that the string s follows the given pattern.文章来源地址https://www.toymoban.com/news/detail-645316.html

Code:
bool wordPattern(char * pattern, char * s) {
    char *words[26];
    for (int i = 0; i < 26; i++) words[i] = NULL;

    char *s_copy = strdup(s);
    char *token = strtok(s_copy, " ");
    int i = 0;

    while (token != NULL) {
        // If the pattern is shorter than the number of words, return false
        if (i >= strlen(pattern)) {
            free(s_copy);
            return false;
        }

        int idx = pattern[i] - 'a';
        if (words[idx] == NULL) {
            // Check if any other character maps to the same word
            for (int j = 0; j < 26; j++) {
                if (words[j] && strcmp(words[j], token) == 0) {
                    free(s_copy);
                    return false;
                }
            }
            words[idx] = token;
        } else {
            if (strcmp(words[idx], token) != 0) {
                free(s_copy);
                return false; // Mismatch in mapping
            }
        }
        token = strtok(NULL, " ");
        i++;
    }

    free(s_copy);

    // Check if pattern length matches the number of words
    if (i != strlen(pattern)) return false;

    return true;
}

到了这里,关于LeetCode //C - 290. Word Pattern的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode 3016. Minimum Number of Pushes to Type Word II

    Leetcode 3016. Minimum Number of Pushes to Type Word II 1. 解题思路 2. 代码实现 题目链接:3016. Minimum Number of Pushes to Type Word II 这道题的话思路其实还是蛮简单的,显然我们的目的是要令对给定的word在键盘上敲击的次数最小。 因此,我们只需要对单词当中按照字符的频次进行倒序排列,

    2024年01月22日
    浏览(46)
  • LeetCode --- 1880. Check if Word Equals Summation of Two Words 解题报告

    The  letter value  of a letter is its position in the alphabet  starting from 0  (i.e.  \\\'a\\\' - 0 ,  \\\'b\\\' - 1 ,  \\\'c\\\' - 2 , etc.). The  numerical value  of some string of lowercase English letters  s  is the  concatenation  of the  letter values  of each letter in  s , which is then  converted  into an integer. For example, if  s = \\\"acb\\\" , we

    2024年02月13日
    浏览(41)
  • 【算法专题--双指针算法】leetcode--283. 移动零、leetcode--1089. 复写零

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月17日
    浏览(42)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(38)
  • LeetCode算法小抄--滑动窗口算法

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计6244字,阅读大概需要3分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ 滑动窗口算法 思路 1、我们在字符串 S 中使用双指针中的

    2023年04月09日
    浏览(38)
  • 6.使用leetcode去练习语言

    目录 1 本章预览 2 简单题举例 2.1 题目描述 2.2 题目解析 2.3 题解 2.4 涉及基础语法 3 中等题举例 3.1 题目描述 3.2 题目解析 3.3 题解 3.4 涉及基础语法 4 本章小结 事实上本章并不会去讲述go语言的基础情况,而是去介绍如何使用Leetcode去帮助我们去学习go语言的基本语法,当然本

    2024年02月08日
    浏览(35)
  • 【C语言】【LeetCode】循环队列

    目录  (一)题目描述 (二)数据结构的选择 (三)函数接口的分析实现  正文开始:         题目链接:622. 设计循环队列         设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循

    2024年03月15日
    浏览(45)
  • 算法沉淀——贪心算法一(leetcode真题剖析)

    贪心算法(Greedy Algorithm)是一种基于贪心策略的优化算法,它通常用于求解最优化问题,每一步都选择当前状态下的最优解,以期望通过局部最优的选择最终达到全局最优。贪心算法的思想是在每一步都做出在当前状态下局部最优的选择,而不考虑未来可能造成的影响。 在

    2024年03月08日
    浏览(48)
  • 算法沉淀——贪心算法六(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/broken-calculator/ 在显示着数字 startValue 的坏计算器上,我们可以执行以下两种操作: **双倍(Double):**将显示屏上的数字乘 2; **递减(Decrement):**将显示屏上的数字减 1 。 给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操

    2024年04月11日
    浏览(43)
  • 算法沉淀——贪心算法七(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/integer-replacement/ 给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2 替换 n 。 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 2^31 - 1 思路 这里我们

    2024年03月23日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包