Dsa

Leetcode solutions Problem 1: Two Sum 1 2 3 4 5 6 7 8 9 10 11 12 class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i in range(0, len(nums)): for j in range(0, len(nums)): if nums[i]+nums[j] == target and i!=j: op = [i,j] return op Problem 2: Roman to integer 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution(object): def romanToInt(self, s): """ :type s: str :rtype: int """ roman = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000,'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900} i = 0 num = 0 while i < len(s): if i+1<len(s) and s[i:i+2] in roman: num+=roman[s[i:i+2]] i+=2 else: #print(i) num+=roman[s[i]] i+=1 return num Problem 3: Pallindrome 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution(object): def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x < 0: return False # Store the number in a variable number = x # This will store the reverse of the number reverse = 0 while number: reverse = reverse * 10 + number % 10 number //= 10 return x == reverse Problem 4: Longest Common Prefix 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ size = len(strs) # if size is 0, return empty string if (size == 0): return "" if (size == 1): return strs[0] # sort the array of strings strs.sort() # find the minimum length from # first and last string end = min(len(strs[0]), len(strs[size - 1])) # find the common prefix between # the first and last string i = 0 while (i < end and strs[0][i] == strs[size - 1][i]): i += 1 pre = strs[0][0: i] return pre Problem 5: Valid Parentheses 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ # Stack for left symbols leftSymbols = [] # Loop for each character of the string for c in s: # If left symbol is encountered if c in ['(', '{', '[']: leftSymbols.append(c) # If right symbol is encountered elif c == ')' and len(leftSymbols) != 0 and leftSymbols[-1] == '(': leftSymbols.pop() elif c == '}' and len(leftSymbols) != 0 and leftSymbols[-1] == '{': leftSymbols.pop() elif c == ']' and len(leftSymbols) != 0 and leftSymbols[-1] == '[': leftSymbols.pop() # If none of the valid symbols is encountered else: return False return leftSymbols == [] Problem 6: Largest Substring Between Two Equal Characters 1 2 3 4 5 6 7 8 class Solution: def maxLengthBetweenEqualCharacters(self, s: str) -> int: output = -1 for i in range (0, len(s)): for j in range (i+1, len(s)): if s[i] == s[j]: output = max(output, j-i-1) return output

A complete guide ds Termwork 1 - Infix evaluation Algorithm Create an empty stack (operandStack) to store operands and an empty stack (operatorStack) to store operators. Initialize a variable (result) to store the final output Iterate through each character of the infix expression. If the current character is an operand, add it to the operandStack. If the current character is an operator, pop operators from operatorStack and add them to operandStack until an operator with lower precedence is found. Then push the current operator onto operatorStack. If the current character is an opening parenthesis, push it onto operatorStack If the current character is a closing parenthesis, pop operators from operatorStack and add them to operandStack until an opening parenthesis is found. Repeat steps 3-7 for all characters of the infix expression. Once all characters have been processed, pop any remaining operators from operatorStack and add them to operandStack. Evaluate the final expression in operandStack and return the result. IO 1 2 3 4 5 6 7 8 9 10 11 12 * ➜ programs git:(ds) ✗ gcc tw1.c -lm && ./a.out * Output 1 * Enter the infix expression to evaluate: 5+7-4+3 * 11 * * Output 2 * Enter the infix expression to evaluate: 6+6 * 12 * * Output 3 * Enter the infix expression to evaluate: 4*6^2 * 256 Applications Expression Evaluation: Stacks are commonly used in the evaluation of mathematical expressions, such as infix and postfix expressions. By using a stack, one can easily convert an infix expression to postfix and then evaluate the postfix expression. This is because stacks provide a last-in-first-out (LIFO) data structure, which is well suited for this type of evaluation. Undo/Redo functionality: Stacks can be used to implement undo and redo functionality in applications, such as text editors and image editors. By maintaining a stack of previous states, the application can easily undo and redo actions, by popping and pushing states from the stack. Syntax Checking: Stacks can be used in parsing and syntax checking of programming languages. For example, in a compiler or interpreter, a stack can be used to keep track of the current state of the program being parsed, such as keeping track of matching brackets or keeping track of function calls. This allows for efficient and accurate checking of the syntax of the program, and aids in error handling. Termwork 2 - infix to postfix Algorithm Create an empty stack. Initialize an empty string (result) to store the postfix expression. Iterate through each character of the prefix expression, starting from the rightmost character. If the current character is an operand, append it to the result string. If the current character is an operator, pop the top two elements from the stack and append them to the result string, separated by the current operator. Then, push the current operator onto the stack. Repeat steps 3-5 for all characters of the prefix expression. Once all characters have been processed, pop any remaining operators from the stack and append them to the result string. Reverse the result string and return it as the postfix expression. IO 1 2 3 4 5 6 7 8 9 10 11 12 * ➜ programs git:(ds) ✗ gcc tw2.c && ./a.out * Output 1 * Enter the exp: 4-6+7*7 * 46-77* * * Output 2 * Enter the exp: 7-4+3^5 * 74-35^ * * Output 3 * Enter the exp: 3+5+4 * 35+4+ Applications Same as termwork 1 ...