Oct 19, 2024 · Oct 19, 2024
diff --git a/Backtracking/WordBreak.js b/Backtracking/WordBreak.js
 /**
 * Determines if the input string can be segmented into words from the provided dictionary.
 * @param {string} s - The input string to be segmented.
 * @param {string[]} wordDict - An array of valid words for segmentation.
 * @returns {boolean} True if the string can be segmented into valid words, false otherwise.
 * @see https://www.geeksforgeeks.org/word-break-problem-using-backtracking/
 */

 export class WordBreakSolution {
  // Function to determine if the input string 's' can be segmented into words from the 'wordDict'
  wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict) // Convert wordDict into a set for efficient lookups
    const memo = Array(s.length).fill(null) // Initialize memoization array to store results of subproblems
    return this.canBreak(0, s, wordSet, memo) // Start the recursive function from the 0th index
  }

  // Helper function to perform recursive backtracking with memoization
  canBreak(start, s, wordSet, memo) {
    if (start === s.length) {
      return true // If we reach the end of the string, return true as we successfully segmented it
    }

    if (memo[start] !== null) {
      return memo[start] // Return the cached result if already computed for this index
    }

    // Explore all possible substrings starting from 'start' index
    for (let end = start + 1; end <= s.length; end++) {
      const currentSubstring = s.slice(start, end) // Get the substring from 'start' to 'end'

      // If the current substring is a valid word and the rest of the string can be broken, return true
      if (
        wordSet.has(currentSubstring) &&
        this.canBreak(end, s, wordSet, memo)
      ) {
        memo[start] = true // Cache the result as true for this index
        return true
      }
    }

    memo[start] = false // Cache the result as false if no valid segmentation found
    return false
  }
 }
diff --git a/Backtracking/tests/WordBreak.test.js b/Backtracking/tests/WordBreak.test.js
 import { describe, it, expect } from 'vitest'
 import { WordBreakSolution } from '../WordBreak'

 describe('Word Break Algorithm', () => {
  it('should return true for valid word segmentation', () => {
    const solution = new WordBreakSolution()
    const result = solution.wordBreak('leetcode', ['leet', 'code'])
    expect(result).toBe(true)
  })

  it('should return false for invalid word segmentation', () => {
    const solution = new WordBreakSolution()
    const result = solution.wordBreak('applepenapple', ['apple', 'pen'])
    expect(result).toBe(true)
  })

  it('should handle edge cases with empty strings', () => {
    const solution = new WordBreakSolution()
    const result = solution.wordBreak('', ['leet', 'code'])
    expect(result).toBe(true)
  })

  it('should return false when no word break is possible', () => {
    const solution = new WordBreakSolution()
    const result = solution.wordBreak('catsandog', [
      'cats',
      'dog',
      'sand',
      'and',
      'cat'
    ])
    expect(result).toBe(false)
  })
 })
diff --git a/package-lock.json b/package-lock.json
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,44 @@
		/**
		* Determines if the input string can be segmented into words from the provided dictionary.
		* @param {string} s - The input string to be segmented.
		* @param {string[]} wordDict - An array of valid words for segmentation.
		* @returns {boolean} True if the string can be segmented into valid words, false otherwise.
		* @see https://www.geeksforgeeks.org/word-break-problem-using-backtracking/
		*/

		export class WordBreakSolution {
		// Function to determine if the input string 's' can be segmented into words from the 'wordDict'
		wordBreak(s, wordDict) {
		const wordSet = new Set(wordDict) // Convert wordDict into a set for efficient lookups
		const memo = Array(s.length).fill(null) // Initialize memoization array to store results of subproblems
		return this.canBreak(0, s, wordSet, memo) // Start the recursive function from the 0th index
		}

		// Helper function to perform recursive backtracking with memoization
		canBreak(start, s, wordSet, memo) {
		if (start === s.length) {
		return true // If we reach the end of the string, return true as we successfully segmented it
		}

		if (memo[start] !== null) {
		return memo[start] // Return the cached result if already computed for this index
		}

		// Explore all possible substrings starting from 'start' index
		for (let end = start + 1; end <= s.length; end++) {
		const currentSubstring = s.slice(start, end) // Get the substring from 'start' to 'end'

		// If the current substring is a valid word and the rest of the string can be broken, return true
		if (
		wordSet.has(currentSubstring) &&
		this.canBreak(end, s, wordSet, memo)
		) {
		memo[start] = true // Cache the result as true for this index
		return true
		}
		}

		memo[start] = false // Cache the result as false if no valid segmentation found
		return false
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,34 @@
		import { describe, it, expect } from 'vitest'
		import { WordBreakSolution } from '../WordBreak'

		describe('Word Break Algorithm', () => {
		it('should return true for valid word segmentation', () => {
		const solution = new WordBreakSolution()
		const result = solution.wordBreak('leetcode', ['leet', 'code'])
		expect(result).toBe(true)
		})

		it('should return false for invalid word segmentation', () => {
		const solution = new WordBreakSolution()
		const result = solution.wordBreak('applepenapple', ['apple', 'pen'])
		expect(result).toBe(true)
		})

		it('should handle edge cases with empty strings', () => {
		const solution = new WordBreakSolution()
		const result = solution.wordBreak('', ['leet', 'code'])
		expect(result).toBe(true)
		})

		it('should return false when no word break is possible', () => {
		const solution = new WordBreakSolution()
		const result = solution.wordBreak('catsandog', [
		'cats',
		'dog',
		'sand',
		'and',
		'cat'
		])
		expect(result).toBe(false)
		})
		})