Fancy DSA Fancy DSA
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)

Jonsam NG

想的更多,也要想的更远
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)
  • 开始上手
  • Plan 计划
  • Roadmap 路线
  • 算法简介
  • Sort 排序

  • Search 搜索

  • Recursive 递归

  • Graph 图

  • Tree 树

  • Math 数学

  • Hash 哈希

  • String 字符串

    • AlphaNumericPalindrome [回文串]
    • AlternativeStringArrange [交替合并字符串]
    • BoyerMoore [博耶-穆尔字符串搜索算法、BM 算法]
    • CheckAnagram [易位构词]
    • NamingConvention [命名规则]
    • CheckExceeding [Exceeding words]
    • CheckPangram [全字母句]
      • 介绍
      • 实现
      • 参考
    • CheckWordOccurrence [单词计数]
    • CountVowels [元音字母计数]
    • CreatePermutations [全排列]
    • DiceCoefficient [Dice系数]
    • FormatPhoneNumber [格式化电话号码]
    • GenerateGUID [生成GUID、UUID]
    • HammingDistance [汉明距离]
    • KMPPatternSearching [KMP字符串匹配]
  • BitManipulation 位操纵

  • Backtracking 回溯

  • DynamicProgramming 动态规划

  • Cache 缓存

  • Array 数组

  • Ciphers 密码学

  • Conversions 转换

  • ProjectEuler 欧拉计划

  • 其他

  • 算法
  • String 字符串
jonsam
2022-09-26
目录

CheckPangram [全字母句]

# 介绍

包含有字母表中所有字母并且言之成义的句子称为全字母句(英语:pangram 或 holoalphabetic sentence,希腊语:pan gramma(意为 “每一个字母”))。全字母句被用于显示字体和测试打字机。英语中最知名的全字母句是 “The quick brown fox jumps over the lazy dog(敏捷的棕色狐狸跳跃过懒惰狗)”。

一般,有趣的全字母句都很短;写出一个包含有最少重复字母的全字母句是一件富有挑战性的工作。长的全字母句在正确的前提下,显著地富有启迪性,或是很幽默,或是很古怪。从某种意义上,全字母句是漏字文(英语:Lipogram)的对立物,因为后者在文章中有意不使用一个或几个特定字母。

# 实现

# JavaScript

检查是否是回文串:

/**
 * What is Pangram?
 * Pangram is a sentence that contains all the letters in the alphabet https://en.wikipedia.org/wiki/Pangram
 */

/**
 * @function checkPangramRegex
 * @description - This function check pangram with the help of regex pattern
 * @param {string} string
 * @returns {boolean}
 * @example - checkPangramRegex("'The quick brown fox jumps over the lazy dog' is a pangram") => true
 * @example - checkPangramRegex('"Waltz, bad nymph, for quick jigs vex." is a pangram') => true
 */
const checkPangramRegex = (string) => {
  if (typeof string !== 'string') {
    throw new TypeError('The given value is not a string')
  }

  /**
   * Match all 26 alphabets using regex, with the help of:
   * Capturing group - () -> Groups multiple tokens together and creates a capture group for extracting a substring or using a backreference.
   * Character set - [a-z] -> Matches a char in the range a to z in case-insensitive for the 'i' flag
   * Negative lookahead - (?!) -> Specifies a group that can not match after the main expression (if it matches, the result is discarded).
   * Dot - . -> Matches any character except linebreaks. Equivalent to
   * Star - * -> Matches 0 or more of the preceding token.
   * Numeric reference - \{$n} -> Matches the results of a capture group. E.g. - \1  matches the results of the first capture group & \3 matches the third.
 */
  return string.match(/([a-z])(?!.*\1)/gi).length === 26
}

/**
 * @function checkPangramSet
 * @description - This function detect the pangram sentence by HashSet
 * @param {string} string
 * @returns {boolean}
 */
const checkPangramSet = (string) => {
  if (typeof string !== 'string') {
    throw new TypeError('The given value is not a string')
  }

  const lettersSet = new Set()

  for (const letter of string.toUpperCase()) {
    if (/[A-Z]/.test(letter)) {
      // if the letter is a valid uppercase alphabet then the add method insert the letter to the HashSet
      lettersSet.add(letter)
    }
  }

  return lettersSet.size === 26
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
  • (?!pattern) :正向否定预查,在任何不匹配 pattern 的字符串开始处匹配查找字符串。这是一个非获取匹配,也就是说,该匹配不需要获取供以后使用。例如 “Windows (?!95|98|NT|2000)" 能 匹配 “Windows 3.1” 中的 “windows”, 但不能匹配 “Windows 2000” 中的 “Windows”。预查不消耗字符,也就是说,在一个匹配发生后,在最后一次匹配之后立即开始下一次匹配的搜索,而不是从包含预查的字符之后开始。参考:正则表达式大全 - 夏夜・梦无眠 (opens new window)
  • Backreferences match the same text as previously matched by a capturing group. The backreference \1 (backslash one) references the first capturing group. 参见:Regex Tutorial - Backreferences To Match The Same Text Again (opens new window)

检查是否可以调整为回文串:

/**
  * What is a palindrome? https://en.wikipedia.org/wiki/Palindrome
  * Receives a string and returns whether it can be rearranged to become a palindrome or not
  * The string can only be a palindrome if the count of ALL characters is even or if the ONLY ONE character count is odd
  * Input is a string
  *
  **/

export const palindromeRearranging = (str) => {
  // check that input is a string
  if (typeof str !== 'string') {
    return 'Not a string'
  }
  // Check if is a empty string
  if (str.length === 0) {
    return 'Empty string'
  }

  // First obtain the character count for each character in the string and store it in an object.
  // Filter the object's values to only the odd character counts.
  const charCounts = [...str].reduce((counts, char) => {
    counts[char] = counts[char] ? counts[char] + 1 : 1
    return counts
  }, {})
  // If the length of the resulting array is 0 or 1, the string can be a palindrome.
  return Object.values(charCounts).filter(count => count % 2 !== 0).length <= 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 参考

  • Pangram - Wikiwand (opens new window)
  • 全字母句 - Wikiwand (opens new window)
编辑 (opens new window)
上次更新: 2022/10/20, 20:03:22
CheckExceeding [Exceeding words]
CheckWordOccurrence [单词计数]

← CheckExceeding [Exceeding words] CheckWordOccurrence [单词计数]→

最近更新
01
0-20题解
10-31
02
本章导读
10-31
03
算法与转换:Part1
10-28
更多文章>
Theme by Vdoing | Copyright © 2022-2022 Fancy DSA | Made by Jonsam by ❤
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式