Skip to main content
Mapagam

Recognizing String Pattern Signals

1. Recognizing Pattern Matching Signal

Signal Type Description Examples Common Patterns
Exact Match Direct string or character sequence match "hello", 'a' Fixed text, literal values
Wildcard Match Flexible pattern with placeholders "h*o", "a?b" Regular expressions, glob patterns
Substring Search Find occurrence within a larger string "world" in "Hello world" Text search, indexing
Regular Expression Complex pattern using regex syntax /\d{4}-\d{2}-\d{2}/ Date formats, email validation
Prefix/Suffix Match Match at beginning or end of string "http://" startsWith "http://" URL schemes, file extensions
Case Insensitive Pattern matching without case sensitivity "Hello" matches "HELLO" i Search engines, user input

Example: Using Wildcard Match

const pattern = "h*o";
const text = "hello world";

// Simple wildcard matching logic
function matchesWildcard(pattern, text) {
  const regex = new RegExp("^" + pattern.replace("*", ".*") + "$");
  return regex.test(text);
}

console.log(matchesWildcard(pattern, text)); // true

const mainString = "The quick brown fox jumps over the lazy dog";
const searchSubstring = "fox";

// Find index of substring
const index = mainString.indexOf(searchSubstring);
console.log(index); // 16

// Check if substring exists
const found = mainString.includes(searchSubstring);
console.log(found); // true
Note: For large texts, consider using optimized search algorithms like KMP or Boyer-Moore for better performance.

2. Recognizing Palindrome Signal

Pattern Description Examples Use Cases
String Reversal Check if a string equals its reverse "racecar", "madam" Text validation, word games
Two Pointers Compare characters from both ends moving inward "abccba" Efficient palindrome checking
Substring Check Verify if any substring is a palindrome "abacabad" Longest palindromic substring problems

Example: Two Pointers Approach

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
}

isPalindrome("racecar"); // true
Note: Case sensitivity and non-alphanumeric characters should be handled based on problem requirements.

3. Recognizing Anagram/Permutation Signal

Signal Description Examples
Character frequency count Same characters with same frequencies in different orders "listen" and "silent"
Substring rearrangement Substring of one string is a permutation of another string "abc" in "bca"
Fixed-size sliding window Looking for a permutation of a pattern in a larger string "ab" in "eidbaooo"

Example: Check if two strings are anagrams

function areAnagrams(s1, s2) {
  if (s1.length !== s2.length) return false;

  const freq = {};
  for (let char of s1) {
    freq[char] = (freq[char] || 0) + 1;
  }

  for (let char of s2) {
    if (!freq[char]) return false;
    freq[char]--;
  }

  return Object.values(freq).every(count => count === 0);
}

// Example usage:
console.log(areAnagrams("listen", "silent")); // true
console.log(areAnagrams("hello", "bello"));   // false

Example: Find all anagrams in a string

function findAnagrams(s, p) {
  const result = [];
  const pCount = {};
  const windowCount = {};

  // Count characters in pattern
  for (let char of p) {
    pCount[char] = (pCount[char] || 0) + 1;
  }

  const windowSize = p.length;

  // Sliding window over string
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    windowCount[char] = (windowCount[char] || 0) + 1;

    // Remove leftmost character if window is too large
    if (i >= windowSize) {
      const leftChar = s[i - windowSize];
      windowCount[leftChar]--;
      if (windowCount[leftChar] === 0) delete windowCount[leftChar];
    }

    // Check if current window matches pattern
    if (i >= windowSize - 1 && JSON.stringify(windowCount) === JSON.stringify(pCount)) {
      result.push(i - windowSize + 1);
    }
  }

  return result;
}

// Example usage:
console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]
Note: Anagram detection often involves character frequency counting or sorting to compare strings.

4. Recognizing Longest Common Subsequence Signal

Signal Description Use Case
Repeated subsequence in two strings When two strings share a common sequence of characters that are not necessarily contiguous Comparing DNA sequences, version control diffs, text similarity
Need to find shared structure Identifying the longest sequence that appears in both strings in the same relative order File comparison tools, plagiarism detection, bioinformatics

Example: Finding LCS in Two Strings

function longestCommonSubsequence(str1, str2) {
  const m = str1.length;
  const n = str2.length;
  const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

const lcsLength = longestCommonSubsequence("ABCDGH", "AEDFHR");
console.log(lcsLength); // Output: 3 (LCS is "ADH")
Note: The LCS problem is a classic dynamic programming pattern. It's often used in diff tools, version control systems like Git, and bioinformatics to compare sequences.

5. Recognizing Longest Increasing Subsequence Signal

Signal Description Indicators
Input Array Sequence of numbers Array with integers or floats
Target Find the longest subsequence with strictly increasing elements Subsequence must maintain relative order but not necessarily contiguous
Output Length of the longest increasing subsequence (LIS) Integer value representing maximum length

Example: Finding LIS in an Array

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
// Expected output: 4 (subsequence: [2, 3, 7, 18] or [2, 3, 7, 101])
Note: The LIS problem is a classic dynamic programming challenge. It can be solved efficiently using binary search with O(n log n) time complexity.

Was this article helpful?

Related Cheat Sheets