2024 June 1 Problems

48 views
Skip to first unread message

daryl...@gmail.com

unread,
Jun 1, 2024, 12:31:18 PMJun 1
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.




Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609
Passcode: 8wf3Qa

Vivek H

unread,
Jun 1, 2024, 1:17:44 PMJun 1
to leetcod...@googlegroups.com
**********************************************************************************************
**********************************************************************************************

class Solution {
public:

    bool isVowelWord(string word) {
        int len = word.length();
        if((word[0] == 'a' || word[0] == 'e' || word[0] == 'i' || word[0] == 'o' || word[0] == 'u') &&
            (word[len-1] == 'a' || word[len-1] == 'e' || word[len-1] == 'i' || word[len-1] == 'o' || word[len-1] == 'u')) {
                return true;
            }
        return false;
    }
    int vowelStrings(vector<string>& words, int left, int right) {

        int count = 0;
        for(int i=left; i<=right; i++) {
            if(isVowelWord(words[i]))
                count++;
        }

        return count;
    }
};

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/7ffc4f09-f1a9-48ae-b863-b1b0fc02212an%40googlegroups.com.

Carlos Green

unread,
Jun 1, 2024, 2:23:48 PMJun 1
to leetcode-meetup
/**
Time O(n) & Space O(1)

* @param {string[]} words
* @param {number} left
* @param {number} right
* @return {number}
*/
var vowelStrings = function(words, left, right) {
let count = 0
const vowels = new Set(['a', 'e', 'i', 'o', 'u'])

for (let i = left; i <= right; i++) {
const first = words[i][0]
const last = words[i][words[i].length - 1]

if (vowels.has(first) && vowels.has(last)) {
count++
}
}
return count
};

vinay

unread,
Jun 2, 2024, 1:05:26 AMJun 2
to leetcod...@googlegroups.com
I applied a top-down DP here and checked all possible partitions and the extra characters that they would generate.
I record the least possible extra chars when an optimal partition happens, and I return that as a result.
I picked hashset for dictionary for faster lookup

time complexity o(n^2) (substring's complexity is o(n), making the total complexity o(n^3))
space complexity o(dictionary.length*each word's length) for the hashset lookup

class Solution {
    Set<String> set = null;
    Integer[] memo = null;

    public int minExtraChar(String s, String[] dictionary) {
        set = new HashSet<>();
        memo = new Integer[s.length()+1];
       
        for(String word : dictionary){
            set.add(word);
        }

        return dp(s, 0);
    }

    public int dp(String s, int index){
        if(index >= s.length()){
            return 0;
        }

        if(memo[index] != null){
            return memo[index];
        }


        int min = Integer.MAX_VALUE;

        for(int i = index; i < s.length(); i++){
            String sub = s.substring(index, i+1);
            if(set.contains(sub)){
                //no extra chars
                min = Math.min(min, dp(s, i+1));
            }else{
                //dp with extra chars
                min = Math.min(min, sub.length()+dp(s, i+1));
            }
        }

        return memo[index] = min;
    }
}


On Sat, Jun 1, 2024 at 9:31 AM daryl...@gmail.com <daryl...@gmail.com> wrote:
--

vinay

unread,
Jun 2, 2024, 1:18:12 AMJun 2
to leetcod...@googlegroups.com
just checking start and end character of each word in the range to be vowel and incrementing the counter as asked
class Solution {
    public int vowelStrings(String[] words, int left, int right) {
        String vowels = "aeiou";

       
        int count = 0;

        for(int i = left; i <= right; i++){
            String s = words[i];
            int start = 0;
            int end = s.length()-1;
            if(vowels.indexOf(s.charAt(start)) >= 0 &&
                vowels.indexOf(s.charAt(end)) >= 0){
                count++;
            }
        }

        return count;
    }
}

Vivek H

unread,
Jun 2, 2024, 6:43:47 PMJun 2
to leetcod...@googlegroups.com
********************************************************************************************************
********************************************************************************************************

similar to Darly's idea of taking a DP array , where DP[i] represents the solution to the min extra chars needed for a string of length i.

/*  Top down memoization approach

Idea  is break the word into two parts
               Part1       Part2
leetscode  ==> [l]          [eetscde]
               [le]         [etscode]
               [lee]        [tscode]


if part1 is found in dictionary, then solution =  solution is just part 2( as min chars left is zero )
if part1 is not found in dictionary, the solution = length of part1(left over chars) + solution to part 2

the final solution will be minimum of all the solutions

Time complexity = O(n2)

*/




class Solution {
public:
    int minExtraCharUtil(string s, int i, int j, map<string, int>& dict,
                         vector<int>& DP) {

        /* we have exhausted the string , so the min left chars is zero */
        if(i > j)
            return 0;
       
        if (DP[i] != -1)
            return DP[i];

        int minVal = INT_MAX;

       
        for (int k = i; k <= j; k++) {
            int val = INT_MAX;

            string str = s.substr(i, k-i+1);
         
            if(dict.count(str)) {
                /*part1 is found in dict */
                val = minExtraCharUtil(s, k+1, j, dict, DP);
            } else {
                /*part1 is not found in dict , so count the left chars and find the solution to part2 */
                val = str.size() + minExtraCharUtil(s, k+1, j, dict, DP);
            }

            minVal = min(minVal, val);

           

        } // for ends
        DP[i] = minVal;
        return DP[i];
    }

    map<string, int> dict;
    int minExtraChar(string s, vector<string>& dictionary) {

        for (int i = 0; i < dictionary.size(); i++) {
            dict[dictionary[i]] = dictionary[i].length();
        }
        int R = s.size();
        vector<int> DP(R, -1);
       
        return minExtraCharUtil(s, 0, R-1 , dict, DP);

    }
};


To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CAMS9BymGcy%2BOgj82c01wj2Nw%3DQdkSsJa98L7v9%2Bt0J4tJuQybA%40mail.gmail.com.

Rudy Talukder

unread,
Jun 5, 2024, 2:03:28 AMJun 5
to leetcod...@googlegroups.com
class Solution: def vowelStrings(self, words: List[str], left: int, right: int) -> int: vowels = ['a','e','i','o','u'] count = 0 for x in range (left,right+1): if ( (len(words[x]) > 1) and (words[x][0] in vowels) and (words[x][-1] in vowels)): count = count + 1 if ( (len(words[x]) == 1) and words[x][0] in vowels): count = count + 1 return count

To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CABDDxtw-z1WWX_20Zx%3DsvD9j7PHkLVqx28H20xueK3aTYZ4xTw%40mail.gmail.com.
Reply all
Reply to author
Forward
0 new messages