Regex in [[ ]] with =~ in Bash Scripting - Time & Space Complexity

Time Complexity: Regex in [[ ]] with =~

O(n)

Understanding Time Complexity

When using regex inside [[ ]] with =~ in bash, it is important to understand how the time to check a match grows as the input changes.

We want to know how the script's running time changes when the input string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

input="$1"
pattern='^[a-z]+$'

if [[ $input =~ $pattern ]]; then
  echo "Match found"
else
  echo "No match"
fi
    

This code checks if the input string contains only lowercase letters using a regex match inside [[ ]] with =~.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine scans each character of the input string to check if it matches the pattern.
• How many times: It processes each character once, moving through the string from start to end.

How Execution Grows With Input

As the input string gets longer, the regex engine checks more characters one by one.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The time to check grows roughly in a straight line with the input length.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the regex match grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "Regex matching inside [[ ]] with =~ is instant no matter how long the input is."

[OK] Correct: The regex engine must look at each character to confirm a match, so longer inputs take more time.

Interview Connect

Understanding how regex matching time grows helps you write efficient scripts and explain your code clearly in interviews.

Self-Check

"What if the regex pattern included nested quantifiers or backreferences? How would the time complexity change?"

Practice

1. What does the expression [[ "hello123" =~ [a-z]+[0-9]+ ]] check in a bash script?

easy

A. If the string is exactly 'hello123'

B. If the string contains letters followed by numbers

C. If the string contains only numbers

D. If the string starts with a number

Solution

1. Step 1: Understand the regex pattern

   The pattern [a-z]+[0-9]+ means one or more lowercase letters followed by one or more digits.

2. Step 2: Apply the pattern to the string

   The string "hello123" starts with letters "hello" and ends with digits "123", so it matches the pattern.

3. Final Answer:

   If the string contains letters followed by numbers -> Option B

4. Quick Check:

   Regex matches letters then digits = A [OK]

Hint: Look for letter-digit sequence in string with regex [OK]

Common Mistakes:

• Thinking quotes are needed around regex inside [[ ]]
• Confusing exact match with pattern match
• Assuming regex matches anywhere without order

2. Which of the following is the correct syntax to test if variable var matches regex ^[0-9]+$ in bash?

easy

A. [[ $var =~ "^[0-9]+$" ]]

B. [[ "$var" =~^[0-9]+$ ]]

C. [[ $var =~ ^[0-9]+$ ]]

D. [[ "$var" =~ "^[0-9]+$" ]]

Solution

1. Step 1: Recall regex syntax in [[ ]]

   Inside [[ ]], the regex pattern should NOT be quoted to work correctly.

2. Step 2: Check each option

   [[ $var =~ ^[0-9]+$ ]] uses [[ $var =~ ^[0-9]+$ ]] without quotes around regex, which is correct syntax.

3. Final Answer:

   [[ $var =~ ^[0-9]+$ ]] -> Option C

4. Quick Check:

   No quotes around regex pattern = B [OK]

Hint: Do not quote regex pattern inside [[ ]] [OK]

Common Mistakes:

• Putting quotes around regex pattern causing syntax errors
• Quoting variable but not regex or vice versa
• Using single brackets [ ] instead of [[ ]]

3. What will be the output of this bash script snippet?

text="abc123"
if [[ $text =~ ^[a-z]+[0-9]+$ ]]; then
  echo "Match"
else
  echo "No match"
fi

medium

A. Match

B. No match

C. Syntax error

D. Empty output

Solution

1. Step 1: Analyze the regex pattern

   The pattern ^[a-z]+[0-9]+$ means the string must start with one or more lowercase letters and end with one or more digits, with nothing else.

2. Step 2: Check the string against the pattern

   The string "abc123" starts with letters "abc" and ends with digits "123", so it matches the pattern exactly.

3. Final Answer:

   Match -> Option A

4. Quick Check:

   String matches regex pattern = D [OK]

Hint: Check start ^ and end $ anchors carefully [OK]

Common Mistakes:

• Ignoring anchors ^ and $ in regex
• Assuming partial match is enough
• Quoting regex pattern causing failure

4. Identify the error in this bash snippet:

input="2023-04-01"
if [[ "$input" =~ "^[0-9]{4}-[0-9]{2}-[0-9]{2}$" ]]; then
  echo "Valid date"
else
  echo "Invalid date"
fi

medium

A. Quotes around regex cause the match to fail

B. Variable input is not quoted

C. Regex pattern is invalid syntax

D. Missing semicolon after if condition

Solution

1. Step 1: Check quoting rules for regex in [[ ]]

   Regex pattern inside [[ ]] with =~ must NOT be quoted; quotes make it a string literal, breaking regex matching.

2. Step 2: Identify the error in the snippet

   The snippet quotes the regex pattern, causing the condition to always fail and print "Invalid date".

3. Final Answer:

   Quotes around regex cause the match to fail -> Option A

4. Quick Check:

   No quotes around regex pattern = C [OK]

Hint: Never quote regex pattern inside [[ ]] [OK]

Common Mistakes:

• Quoting regex pattern inside [[ ]]
• Forgetting to quote variable when needed
• Assuming regex syntax errors without checking quotes

5. You want to check if a variable filename ends with either ".jpg" or ".png" using regex in bash. Which condition correctly tests this?

hard

A. [[ "$filename" =~ "\.(jpg|png)$" ]]

B. [[ $filename =~ "\.(jpg|png)$" ]]

C. [[ "$filename" =~\.(jpg|png)$ ]]

D. [[ $filename =~ \.(jpg|png)$ ]]

Solution

1. Step 1: Understand regex for file extensions

   The pattern \.(jpg|png)$ matches a dot followed by 'jpg' or 'png' at the end of the string.

2. Step 2: Apply correct quoting rules

   Regex pattern must NOT be quoted inside [[ ]], and variable can be unquoted if it has no spaces. [[ $filename =~ \.(jpg|png)$ ]] correctly uses unquoted regex and variable.

3. Final Answer:

   [[ $filename =~ \.(jpg|png)$ ]] -> Option D

4. Quick Check:

   Unquoted regex with alternation = A [OK]

Hint: Use unquoted regex with alternation inside [[ ]] [OK]

Common Mistakes:

• Quoting regex pattern causing failure
• Not escaping dot before extension
• Quoting variable unnecessarily