abbreviation.cpp File Reference

Implementation of Abbrievation More...

#include <cassert>
#include <iostream>
#include <string>
#include <vector>

Include dependency graph for abbreviation.cpp:

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	abbreviation
	Functions for Abbreviation implementation.

Functions
bool	dynamic_programming::abbreviation::abbreviation_recursion (std::vector< std::vector< bool > > *memo, std::vector< std::vector< bool > > *visited, const std::string &str, const std::string &result, uint32_t str_idx=0, uint32_t result_idx=0)
	Recursive Dynamic Programming function. More...
bool	dynamic_programming::abbreviation::abbreviation (const std::string &str, const std::string &result)
	Iterative Dynamic Programming function. More...
static void	test ()
	Self test-implementations. More...
int	main ()
	Main function. More...

Detailed Description

Implementation of Abbrievation

Given two strings, a and b, determine if it's possible to make a equal to b You can perform the following operations on the string a:

1. Capitalize zero or more of a's lowercase letters.
2. Delete all of the remaining lowercase letters in a.

Algorithm

The idea is in the problem statement itself: iterate through characters of string a and b (for character indexes i and j respectively):

1. If a[i] and b[j] are equal, then move to next position
2. If a[i] is lowercase of b[j], then explore two possibilities: a. Capitalize a[i] or b. Skip a[i]
3. If the a[i] is not uppercase, just discard that character, else return false

Time Complexity: (O(|a|*|b|)) where |a| => length of string a

Author

Ashish Daulatabad

Function Documentation

abbreviation()

bool dynamic_programming::abbreviation::abbreviation	(	const std::string &	str,
		const std::string &	result
	)

Iterative Dynamic Programming function.

Returns whether s can be converted to t with following rules: a. Capitalize zero or more of s's lowercase letters from string s b. remove all other lowercase letters from string s Note: The transition states for iterative is similar to recursive as well

Parameters

str	given string, which might not be abbreivated
result	resultant abbreivated string

Returns

false if string str cannot be converted to result

true if string str can be converted to result

                                                                 {
    std::vector<std::vector<bool>> memo(
        str.size() + 1, std::vector<bool>(result.size() + 1, false));
 
    for (uint32_t i = 0; i <= str.size(); ++i) {
        memo[i][0] = true;
    }
    for (uint32_t i = 1; i <= result.size(); ++i) {
        memo[0][i] = false;
    }
    for (uint32_t i = 1; i <= str.size(); ++i) {
        for (uint32_t j = 1; j <= result.size(); ++j) {
            if (str[i - 1] == result[j - 1]) {
                memo[i][j] = memo[i - 1][j - 1];
            } else if (str[i - 1] - 32 == result[j - 1]) {
                memo[i][j] = (memo[i - 1][j - 1] || memo[i - 1][j]);
            } else {
                if (str[i - 1] >= 'A' && str[i - 1] <= 'Z') {
                    memo[i][j] = false;
                } else {
                    memo[i][j] = memo[i - 1][j];
                }
            }
        }
    }
    return memo.back().back();
}

Here is the call graph for this function:

abbreviation_recursion()

bool dynamic_programming::abbreviation::abbreviation_recursion	(	std::vector< std::vector< bool > > *	memo,
		std::vector< std::vector< bool > > *	visited,
		const std::string &	str,
		const std::string &	result,
		uint32_t	str_idx = 0,
		uint32_t	result_idx = 0
	)

Recursive Dynamic Programming function.

Returns whether s can be converted to t with following rules: a. Capitalize zero or more of a's lowercase letters from string s b. remove all other lowercase letters from string s

Parameters

memo	To store the result
visited	boolean to check if the result is already computed
str	given string, which might not be abbreivated
result	resultant abbreivated string
str_idx	index for string str, helpful for transitions
result_idx	index for string result, helpful for transitions

Returns

false if string str cannot be converted to result

true if string str can be converted to result

(str[i] == result[j]): if str char at position i is equal to result char at position j, then s character is a capitalized one, move on to next character str[i] - 32 == result[j]: if str[i] character is lowercase of result[j] then explore two possibilites:

1. convert it to capitalized letter and move both to next pointer (i + 1, j + 1)
2. Discard the character (str[i]) and move to next char (i + 1, j)

                                                                           {
    bool ans = memo->at(str_idx).at(result_idx);
    if (str_idx == str.size() && result_idx == result.size()) {
        return true;
    } else if (str_idx == str.size() && result_idx != result.size()) {
        // result `t` is not converted, return false
        return false;
    } else if (!visited->at(str_idx).at(result_idx)) {
        /**
         * `(str[i] == result[j])`: if str char at position i is equal to
         * `result` char at position j, then s character is a capitalized one,
         * move on to next character `str[i] - 32 == result[j]`:
         * if `str[i]` character is lowercase of `result[j]` then explore two
         * possibilites:
         * 1. convert it to capitalized letter and move both to next pointer
         * `(i + 1, j + 1)`
         * 2. Discard the character `(str[i])` and move to next char `(i + 1,
         * j)`
         */
        if (str[str_idx] == result[result_idx]) {
            ans = abbreviation_recursion(memo, visited, str, result,
                                         str_idx + 1, result_idx + 1);
        } else if (str[str_idx] - 32 == result[result_idx]) {
            ans = abbreviation_recursion(memo, visited, str, result,
                                         str_idx + 1, result_idx + 1) ||
                  abbreviation_recursion(memo, visited, str, result,
                                         str_idx + 1, result_idx);
        } else {
            // if `str[i]` is uppercase, then cannot be converted, return
            // `false`
            // else `str[i]` is lowercase, only option is to discard this
            // character
            if (str[str_idx] >= 'A' && str[str_idx] <= 'Z') {
                ans = false;
            } else {
                ans = abbreviation_recursion(memo, visited, str, result,
                                             str_idx + 1, result_idx);
            }
        }
    }
    (*memo)[str_idx][result_idx] = ans;
    (*visited)[str_idx][result_idx] = true;
    return (*memo)[str_idx][result_idx];
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self test-implementations.

Returns

void

                   {
    std::string s = "daBcd", t = "ABC";
    std::vector<std::vector<bool>> memo(s.size() + 1,
                                        std::vector<bool>(t.size() + 1, false)),
        visited(s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    assert(dynamic_programming::abbreviation::abbreviation_recursion(
               &memo, &visited, s, t) == true);
    assert(dynamic_programming::abbreviation::abbreviation(s, t) == true);
    s = "XXVVnDEFYgYeMXzWINQYHAQKKOZEYgSRCzLZAmUYGUGILjMDET";
    t = "XXVVDEFYYMXWINQYHAQKKOZEYSRCLZAUYGUGILMDETQVWU";
    memo = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    visited = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    assert(dynamic_programming::abbreviation::abbreviation_recursion(
               &memo, &visited, s, t) == false);
    assert(dynamic_programming::abbreviation::abbreviation(s, t) == false);
 
    s = "DRFNLZZVHLPZWIupjwdmqafmgkg";
    t = "DRFNLZZVHLPZWI";
 
    memo = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    visited = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    assert(dynamic_programming::abbreviation::abbreviation_recursion(
               &memo, &visited, s, t) == true);
    assert(dynamic_programming::abbreviation::abbreviation(s, t) == true);
}

Here is the call graph for this function: