Python ALL Eyes on Strings- String Data Type & For Loop Combined

Good Examples

1.To find is a given string starts with a vowel.

def startsWithVowel(str1):
	if str1[0] in "aeiouAEIOU":
		return True
	return False

startsWithVowel("Apple")
True
startsWithVowel("banana")
False

2.How to check if words are anagram Show ?

Here are two effective ways to check if two words are anagrams in Python:

Method 1: Sorting

This approach sorts both words alphabetically and then compares them. If the sorted strings are equal, they are anagrams.

def is_anagram_sort(str1, str2):
  """
  Checks if two strings are anagrams using sorting

  Args:
      str1: First string
      str2: Second string

  Returns:
      True if anagrams, False otherwise
  """
  # Convert both strings to lowercase and remove whitespaces (optional)
  str1 = str1.lower().replace(" ", "")
  str2 = str2.lower().replace(" ", "")

  # Check if lengths are equal (anagrams must have the same number of characters)
  if len(str1) != len(str2):
    return False

  # Sort both strings
  sorted_str1 = sorted(str1)
  sorted_str2 = sorted(str2)

  # Compare the sorted strings
  return sorted_str1 == sorted_str2

# Example usage
str1 = "race"
str2 = "care"
if is_anagram_sort(str1, str2):
  print(str1, "and", str2, "are anagrams")
else:
  print(str1, "and", str2, "are not anagrams")

Explanation:

1. The function is_anagram_sort takes two strings (str1 and str2) as input.
2. It converts both strings to lowercase and removes whitespaces (optional) for case-insensitive and whitespace-insensitive comparison.
3. It checks if the lengths of the strings are equal. If not, they cannot be anagrams.
4. It sorts both strings using sorted(). Sorting rearranges the characters alphabetically.
5. It compares the sorted strings to see if they are identical. If so, the original strings are anagrams.

Method 2: Counting Characters

This method uses a dictionary to count the occurrences of each character in both strings. If the resulting dictionaries are the same, the strings are anagrams.

from collections import Counter

def is_anagram_count(str1, str2):
  """
  Checks if two strings are anagrams using character counting

  Args:
      str1: First string
      str2: Second string

  Returns:
      True if anagrams, False otherwise
  """
  # Convert both strings to lowercase and remove whitespaces (optional)
  str1 = str1.lower().replace(" ", "")
  str2 = str2.lower().replace(" ", "")

  # Create dictionaries to count character occurrences
  char_count_str1 = Counter(str1)
  char_count_str2 = Counter(str2)

  # Compare the dictionaries
  return char_count_str1 == char_count_str2

# Example usage
str1 = "listen"
str2 = "silent"
if is_anagram_count(str1, str2):
  print(str1, "and", str2, "are anagrams")
else:
  print(str1, "and", str2, "are not anagrams")

Explanation:

1. The function is_anagram_count takes two strings (str1 and str2) as input.
2. It converts both strings to lowercase and removes whitespaces (optional) for case-insensitive and whitespace-insensitive comparison.
3. It uses Counter from the collections library to create dictionaries for each string. Each key in the dictionary represents a character, and the value represents the number of times that character appears in the string.
4. It compares the two dictionaries using the equality operator (==). If the dictionaries have the same keys (characters) with the same corresponding values (occurrences), the strings are anagrams.

3.To check if a word has double consecutive letters.

def hasDouble(str1):
    str1 = str1.lower()
    flag = False
    for i in str1[0:len(str1)-1]:
        index = str1.index(i)
        if i==str1[index+1]:
            flag = True
    return flag 

 hasDouble("Google")
True
 hasDouble("Microsoft")
False

Really Good Examples

1.How to check if a string is palindrome in python

:-

You can check if a string is a palindrome in Python by comparing the string with its reverse. If the string is the same when reversed, it’s a palindrome. Here’s a simple way to do it:

def is_palindrome(s):
    # Remove spaces and convert to lowercase for case-insensitive comparison
    s = s.replace(" ", "").lower()
    # Compare the string with its reverse
    return s == s[::-1]

# Test the function
print(is_palindrome("radar"))  # Output: True
print(is_palindrome("hello"))  # Output: False

This function is_palindrome() takes a string s as input, removes spaces and converts it to lowercase for case-insensitive comparison. Then, it compares the original string s with its reverse using slicing s[::-1]. If they are equal, the function returns True, indicating that the string is a palindrome; otherwise, it returns False.

OneLiner

s=’wew’

s==s.replace(” “,””).lower()[::-1]

2. Transform to pig Latin

Pig Latin: simple text transformation that modifies each word moving the first character to the end and appending “ay” to the end.

You can create a Python function to convert text into Pig Latin by following these steps:

1. Split the text into words.
2. For each word:
   • Move the first character to the end of the word.
   • Append “ay” to the end of the word.
3. Join the modified words back into a single string.

Here’s the implementation of the function:

def pig_latin(text):
    # Split the text into words
    words = text.split()
    # List to store Pig Latin words
    pig_latin_words = []
    # Iterate over each word
    for word in words:
        # Move the first character to the end and append "ay"
        pig_latin_word = word[1:] + word[0] + "ay"
        # Append the modified word to the list
        pig_latin_words.append(pig_latin_word)
    # Join the Pig Latin words back into a single string
    pig_latin_text = " ".join(pig_latin_words)
    return pig_latin_text

# Test the function
text = "hello world"
print(pig_latin(text))  # Output: "ellohay orldway"

This function splits the input text into words, processes each word to convert it into Pig Latin, and then joins the modified words back into a single string. You can test it with different input texts to see how it transforms them into Pig Latin.

3.To calculate prefix and suffix scores for string comparisons. The prefix score is the length of the longest common prefix, and the suffix score is the length of the longest common suffix between two strings.

def prefix_score(s1, s2):
    score = 0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]:
            score += 1
        else:
            break
    return score

def suffix_score(s1, s2):
    score = 0
    for i in range(1, min(len(s1), len(s2)) + 1):
        if s1[-i] == s2[-i]:
            score += 1
        else:
            break
    return score

# Example usage
s1 = 'ram'
s2 = 'rafgert'
s3 = 'genam'

print("Prefix score of s1 and s2:", prefix_score(s1, s2))  # Output: 2
print("Suffix score of s1 and s3:", suffix_score(s1, s3))  # Output: 2

4.Longest Common Subsequence (LCS)

The longest common subsequence problem is to find the longest subsequence common to all sequences in a set of sequences (often just two sequences). A subsequence is a sequence that appears in the same relative order, but not necessarily consecutively.

Problem Description

Given two strings, write a Python function to find the length of their longest common subsequence. For example, for the strings s1 = "ABCBDAB" and s2 = "BDCAB", the longest common subsequence is "BDAB" or "BCAB", and its length is 4.

Solution

We’ll use dynamic programming to solve this problem efficiently.

def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    # Create a 2D array to store lengths of longest common subsequence.
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Build the dp array from the bottom up.
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # dp[m][n] contains the length of LCS for s1 and s2.
    return dp[m][n]

# Example usage
s1 = "ABCBDAB"
s2 = "BDCAB"
print("Length of LCS:", lcs_length(s1, s2))  # Output: 4

def lcs_dp(X, Y):
  """
  Finds the length and sequence of LCS using dynamic programming

  Args:
      X: First string
      Y: Second string

  Returns:
      Length of the LCS and the LCS sequence
  """
  m = len(X)
  n = len(Y)

  # Create a table to store LCS lengths
  lcs_table = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

  # Fill the table using dynamic programming
  for i in range(m + 1):
    for j in range(n + 1):
      if i == 0 or j == 0:
        lcs_table[i][j] = 0
      elif X[i-1] == Y[j-1]:
        lcs_table[i][j] = lcs_table[i-1][j-1] + 1
      else:
        lcs_table[i][j] = max(lcs_table[i-1][j], lcs_table[i][j-1])

  # Backtrack to find the LCS sequence
  lcs = ""
  i = m
  j = n
  while i > 0 and j > 0:
    if X[i-1] == Y[j-1]:
      lcs = X[i-1] + lcs
      i -= 1
      j -= 1
    else:
      if lcs_table[i-1][j] > lcs_table[i][j-1]:
        i -= 1
      else:
        j -= 1

  # Return the length and the LCS sequence (reversed)
  return lcs_table[m][n], lcs[::-1]

# Example usage
X = "AGGTAB"
Y = "GXTXAYB"
lcs_length, lcs_sequence = lcs_dp(X, Y)
print("Length of LCS:", lcs_length)
print("LCS sequence:", lcs_sequence)

Explanation

1. Initialization: We initialize a 2D list dp of size (m+1) x (n+1) where m and n are the lengths of the input strings. Each entry dp[i][j] will store the length of the LCS of the substrings s1[0..i-1] and s2[0..j-1].
2. Filling the DP Table: We iterate over each character of both strings. If the characters match, we add 1 to the value of the diagonal cell (dp[i-1][j-1]). If they don’t match, we take the maximum value from the cell above (dp[i-1][j]) or the cell to the left (dp[i][j-1]).
3. Result: The value at dp[m][n] will contain the length of the LCS of the two input strings.

This approach ensures we compute the LCS length efficiently with a time complexity of O(m*n) and a space complexity of O(m*n).

Recursive Approach:

This method breaks down the problem into smaller subproblems and builds the solution from the bottom up. Here’s the implementation:

def lcs_recursive(X, Y, m, n):
  """
  Finds the length of LCS using recursion

  Args:
      X: First string
      Y: Second string
      m: Length of first string
      n: Length of second string

  Returns:
      Length of the LCS
  """
  if m == 0 or n == 0:
    return 0
  if X[m-1] == Y[n-1]:
    return 1 + lcs_recursive(X, Y, m-1, n-1)
  else:
    return max(lcs_recursive(X, Y, m-1, n), lcs_recursive(X, Y, m, n-1))

# Example usage
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
lcs_length = lcs_recursive(X, Y, m, n)
print("Length of LCS:", lcs_length)

Explanation:

• The function lcs_recursive takes four arguments:
  • X: First string
  • Y: Second string
  • m: Length of X
  • n: Length of Y
• The base case checks if either string is empty. If so, the LCS length is 0.
• If the last characters of both strings match, the LCS length is 1 plus the LCS length of the shorter strings (X[0:m-1] and Y[0:n-1]).
• If the last characters don’t match, the LCS length is the maximum of the LCS lengths of considering either string one character shorter (excluding the last character).

5. Longest Palindromic Substring

Given a string, find the longest substring which is a palindrome. For example, given the string “babad”, the longest palindromic substring is “bab” (or “aba”).

def longest_palindromic_substring(s):
    n = len(s)
    if n == 0:
        return ""
    
    # Table to store lengths of palindromic substrings
    dp = [[False] * n for _ in range(n)]
    
    start = 0
    max_length = 1
    
    # All substrings of length 1 are palindromic
    for i in range(n):
        dp[i][i] = True
    
    # Check for substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2
    
    # Check for lengths greater than 2
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # Checking for palindromic substring
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > max_length:
                    start = i
                    max_length = length
    
    return s[start:start + max_length]

# Example usage
s = "babad"
print("Longest Palindromic Substring:", longest_palindromic_substring(s))  # Output: "bab" or "aba"

6. Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'. '.' matches any single character, and '*' matches zero or more of the preceding element.

def is_match(s, p):
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[0][0] = True

    for i in range(1, len(p) + 1):
        if p[i - 1] == '*':
            dp[0][i] = dp[0][i - 2]

    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                dp[i][j] = dp[i][j - 2]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
    return dp[-1][-1]

# Example usage
s = "aab"
p = "c*a*b"
print("Regular Expression Match:", is_match(s, p))  # Output: True

7. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""
    
    dict_t = Counter(t)
    required = len(dict_t)
    
    l, r = 0, 0
    formed = 0
    window_counts = {}
    
    ans = float("inf"), None, None
    
    while r < len(s):
        character = s[r]
        window_counts[character] = window_counts.get(character, 0) + 1
        
        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1
        
        while l <= r and formed == required:
            character = s[l]
            
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)
            
            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1
            
            l += 1
        
        r += 1
    
    return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

# Example usage
s = "ADOBECODEBANC"
t = "ABC"
print("Minimum Window Substring:", min_window(s, t))  # Output: "BANC"

8.Balanced Parentheses:

1. Balanced Parentheses:

• Problem: Given a string of parentheses ((), {}, []), determine if the parentheses are balanced. A string is balanced if each opening parenthesis has a corresponding closing parenthesis of the same type and in the correct order.
• Example:
  • Input: "{[]}" (balanced)
  • Input: "([)]" (unbalanced)
• Challenge: Solve this efficiently using a stack or recursion.

Solution (Stack Approach):

def is_balanced(expression):
  """
  Checks if the parentheses in a string are balanced

  Args:
      expression: String containing parentheses

  Returns:
      True if balanced, False otherwise
  """
  mapping = {"(": ")", "{": "}", "[": "]"}  # Mapping for opening and closing parentheses
  stack = []
  for char in expression:
    if char in mapping:  # If it's an opening parenthesis, push it onto the stack
      stack.append(char)
    else:  # If it's a closing parenthesis
      if not stack or mapping[stack.pop()] != char:  # Check if it matches the top of the stack
        return False
  return not stack  # If the stack is empty at the end, all parentheses were balanced

# Example usage
expression = "{[]}"
if is_balanced(expression):
  print("Balanced parentheses")
else:
  print("Unbalanced parentheses")

9. Group Shifted Strings :

• Problem: Given an array of strings, group all strings where shifting each letter to the left by one position results in strings in the group.
• Example:
  • Input: ["abc", "bcd", "abcde", "bcdx"]
  • Output: [["abc", "bcd"], ["abcde"]] (Explanation: “bcd” is one shift to the left of “abc”, and “bcdx” doesn’t follow the pattern)
• Challenge: Solve this efficiently in time and space complexity. Consider using a hash table or rolling hash function.

Solution (Hash Table Approach):

Python

from collections import defaultdict  # Use defaultdict for efficient key creation

def group_shifted_strings(strs):
  """
  Groups strings where shifting letters to the left by one position results in strings in the group

  Args:
      strs: Array of strings

  Returns:
      List of lists, where each inner list contains grouped strings
  """
  groups = defaultdict(list)
  for word in strs:
    # Create a key by shifting each character and constructing a new string
    key = ''.join([chr((ord(char) - ord('a') + 1) % 26 + ord('a')) for char in word])
    groups[key].append(word)
  return list(groups.values())

# Example usage
strs = ["abc", "bcd", "abcde", "bcdx"]
groups = group_shifted_strings(strs)
print("Grouped strings:", groups)

10. Reverse Words in a String (with Spaces):

• Problem: Given a string, reverse the words in place without using any temporary data structures (like a second string).
• Example:
  • Input: “This is a string”
  • Output: “string a is This”
• Challenge: Solve this in-place with a two-pointer approach.

Solution (Two-Pointer Approach):

def reverse_words(s):
  """
  Reverses the words in a string in-place

  Args:
      s: String to be reversed
  """
  s = list(s)  # Convert string to a list for in-place modification
  n = len(s)

  # Reverse the entire string first
  i, j = 0, n - 1
  while i < j:
    s[i], s[j] = s[j], s[i]
    i += 1
    j -= 1

  # Reverse individual words within the reversed string
  start = 0
  for i in range(n):
    if s[i] == " ":
      end = i
      # Reverse the word from start to end-1 (excluding the space)
      j = start
      k = end - 1
      while j < k:
        s[j], s[k] = s[k], s

Head to Next