Given an integer n. Return the nth row of the following look-and-say pattern.
1
11
21
1211
111221
Look-and-Say Pattern:
To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:
	1 is read off as "one 1" or 11.
	11 is read off as "two 1s" or 21.
	21 is read off as "one 2, then one 1" or 1211.
	1211 is read off as "one 1, one 2, then two 1s" or 111221.
	111221 is read off as "three 1s, two 2s, then one 1" or 312211.
Example 1:
Input:
n = 5
Output: 111221
Explanation: The 5^{th} row of the given pattern
will be 111221.
Example 2:
Input:
n = 3
Output: 21
Explanation: The 3^{rd} row of the given pattern
will be 21.
Your Task:  
You dont need to read input or print anything. Complete the function lookandsay() which takes integer n as input parameter and returns a string denoting the contents of the nth row of given pattern.
Expected Time Complexity: O(2^{n})
Expected Auxiliary Space: O(2^{n-1})  
Constraints:
1 ≤ n ≤ 30

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(2^{n})
Expected Auxiliary Space: O(2^{n-1})

Starter code:
#User function Template for python3



class Solution:



    def lookandsay(self, n):

        # code here

Solutions:
class Solution:

	def lookandsay(self, n):
		if n == 1:
			return 1
		val = '11'
		for i in range(n - 2):
			s = ''
			c = 1
			val = str(val)
			for i in range(len(val) - 1):
				if val[i] == val[i + 1]:
					c += 1
				else:
					s += str(c) + val[i]
					c = 1
			s += str(c) + val[i + 1]
			val = s
		return val


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 11
		t = '11'
		s = ''
		for i in range(3, n + 1):
			count = 1
			s = ''
			for j in range(1, len(t)):
				if t[j] == t[j - 1]:
					count = count + 1
				else:
					s = s + str(count)
					s = s + t[j - 1]
					count = 1
			s = s + str(count)
			s = s + t[j]
			t = s
		return t


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		if n == 2:
			return '11'
		s = '11'
		for i in range(3, n + 1):
			s += '$'
			l = len(s)
			cnt = 1
			tmp = ''
			for j in range(1, l):
				if s[j] != s[j - 1]:
					tmp += str(cnt + 0)
					tmp += s[j - 1]
					cnt = 1
				else:
					cnt += 1
			s = tmp
		return s


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		res = self.lookandsay(n - 1)
		res = str(res)
		count = 0
		ans = ''
		for i in range(0, len(res)):
			count += 1
			if i == len(res) - 1 or res[i] != res[i + 1]:
				ans += str(count) + res[i]
				count = 0
		return ans


class Solution:

	def lookandsay(self, n):
		zzz = int(n)
		if zzz == 1:
			return '1'
		if zzz == 2:
			return '11'
		if zzz == 3:
			return '21'
		if zzz == 4:
			return '1211'
		p = '1211'
		for k in range(4, int(n)):
			count = 1
			z = ''
			for i in range(len(p) - 1):
				if p[i] == p[i + 1]:
					count += 1
				else:
					z += str(count)
					count = 1
			q = ''
			for i in p:
				if i not in q or q[len(q) - 1] != i:
					q += i
			z += str(count)
			xx = ''
			for i in range(len(q)):
				xx += z[i] + q[i]
			p = xx
		if p != '1211':
			return p


class Solution:

	def lookandsay(self, n):
		look = '1'
		for i in range(n - 1):
			say = ''
			count = 1
			current = look[0]
			for k in look[1:]:
				if k == current:
					count += 1
				else:
					say += str(count) + current
					count = 1
					current = k
			say += str(count) + current
			look = say
		return look


class Solution:

	def solveTab(self, n):
		dp = [''] * (n + 1)
		dp[1] = '1'
		for i in range(2, n + 1):
			s = dp[i - 1]
			res = ''
			count = 0
			for j in range(len(s)):
				count += 1
				if j == len(s) - 1 or s[j] != s[j + 1]:
					res = res + str(count) + s[j]
					count = 0
			dp[i] = res
		return dp[n]

	def lookandsay(self, n):
		return self.solveTab(n)


class Solution:

	def lookandsay(self, n):
		first = '1'
		for i in range(n - 1):
			new = ''
			count = 1
			current = first[0]
			for c in first[1:]:
				if c == current:
					count += 1
				else:
					new += str(count) + current
					current = c
					count = 1
			new += str(count) + current
			first = new
		return first


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		if n == 2:
			return '11'
		s = '11'
		for i in range(3, n + 1):
			temp = ''
			s = s + '$'
			count = 1
			for k in range(1, len(s)):
				if s[k] != s[k - 1]:
					temp = temp + str(count)
					temp = temp + s[k - 1]
					count = 1
				else:
					count = count + 1
			s = temp
		return s


class Solution:

	def solveMem(self, n, dp):
		if n == 1:
			return '1'
		if dp[n] != -1:
			return dp[n]
		s = self.solveMem(n - 1, dp)
		res = ''
		count = 0
		for i in range(len(s)):
			count += 1
			if i == len(s) - 1 or s[i] != s[i + 1]:
				res = res + str(count) + s[i]
				count = 0
		dp[n] = res
		return dp[n]

	def lookandsay(self, n):
		dp = [-1] * (n + 1)
		return self.solveMem(n, dp)


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		elif n == 2:
			return '11'
		start = '11'
		for i in range(n - 2):
			j = 0
			new_str = ''
			while j < len(start):
				k = j + 1
				count = 1
				while k < len(start) and start[j] == start[k]:
					k += 1
					count += 1
				new_str += str(count) + start[j]
				if count == 1:
					j += 1
				else:
					j = k
			start = new_str
		return start


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		l = ['1']
		for i in range(1, n):
			s = ''
			k = 0
			m = l[i - 1][0]
			d = {}
			for j in range(0, len(l[i - 1])):
				if m == l[i - 1][j]:
					k += 1
				else:
					s += str(k) + m
					m = l[i - 1][j]
					k = 1
			s += str(k) + m
			l.append(s)
		return l[n - 1]


class Solution:

	def lookandsay(self, n):
		j = 1
		k = '1'
		s = ''
		while j < n:
			c = 1
			if k == '1':
				s = '11'
			elif len(k) > 1:
				s = ''
				d = 0
				i = 0
				while i < len(k) - 1:
					start = i
					f = 0
					while i < len(k) - 1 and k[i + 1] == k[i]:
						c += 1
						i += 1
						f = 1
					if f == 1:
						s = s + str(i - start + 1) + k[start]
						c = 1
						if i != len(k) - 1:
							i += 1
					else:
						s = s + str(c) + k[i]
						c = 1
						i += 1
				if k[-1] != k[-2]:
					s = s + '1' + k[-1]
			k = s
			j += 1
		return k


class Solution:

	def rec(self, st, n, ans):
		if n - 1 == 0:
			ans += st
			return
		count = 1
		lis = []
		for i in range(len(st) - 1):
			if st[i] == st[i + 1]:
				count += 1
			else:
				lis.append(str(count))
				lis.append(st[i])
				count = 1
		lis.append(str(count))
		lis.append(st[-1])
		self.rec(lis, n - 1, ans)

	def lookandsay(self, n):
		st = '1'
		ans = []
		self.rec(st, n, ans)
		ans = ''.join(ans)
		return ans


class Solution:

	def lookandsay(self, n):
		answer = [1]
		for _ in range(n - 1):
			answer = self.spell(answer)
		return ''.join([str(x) for x in answer])

	def spell(self, num):
		answer = []
		prev = -1
		count = 0
		for i in range(len(num)):
			if num[i] != prev:
				if count != 0:
					answer.append(count)
					answer.append(prev)
				prev = num[i]
				count = 1
			else:
				count += 1
		answer.append(count)
		answer.append(prev)
		return answer


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		if n == 2:
			return '11'
		temp = '11'
		for i in range(3, n + 1):
			res = ''
			temp += '$'
			c = 1
			for k in range(1, len(temp)):
				if temp[k] == temp[k - 1]:
					c += 1
				else:
					res += str(c) + temp[k - 1]
					c = 1
			temp = res
		return temp


class Solution:

	def help(self, s, n, res):
		if n - 1 == 0:
			res += s
			return
		c = 1
		a = []
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				c += 1
			else:
				a.append(str(c))
				a.append(s[i])
				c = 1
		a.append(str(c))
		a.append(s[-1])
		self.help(a, n - 1, res)

	def lookandsay(self, n):
		s = '1'
		a = []
		self.help(s, n, a)
		res = ''.join(a)
		return res


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		elif n == 2:
			return '11'
		else:
			first_str = '11'
			new_str = ''
			for i in range(1, n - 1):
				ch = ''
				count = 0
				j = 0
				while j <= len(first_str) - 1:
					new_ch = first_str[j]
					if j == 0:
						ch = new_ch
						count += 1
					elif ch == new_ch:
						count += 1
					else:
						new_str += str(count)
						new_str += ch
						ch = new_ch
						count = 1
					j += 1
				if count > 0:
					new_str += str(count) + str(ch)
				first_str = new_str
				new_str = ''
		return first_str


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		p = self.lookandsay(n - 1)
		ans = ''
		c = 1
		for i in range(len(p)):
			if i == len(p) - 1 or p[i] != p[i + 1]:
				ans += str(c) + p[i]
				c = 1
			else:
				c += 1
		return ans


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		s = self.lookandsay(n - 1)
		ans = ''
		counter = 0
		for i in range(len(s)):
			counter += 1
			if i == len(s) - 1 or s[i] != s[i + 1]:
				ans += str(counter) + s[i]
				counter = 0
		return ans


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 11
		s = '11'
		dmy = ''
		for i in range(2, n):
			cnt = 1
			for i in range(1, len(s)):
				if s[i] == s[i - 1]:
					cnt += 1
					if len(s) == i + 1:
						dmy = dmy + str(cnt) + s[i - 1]
						cnt = 1
				else:
					dmy = dmy + str(cnt) + s[i - 1]
					cnt = 1
					if len(s) == i + 1:
						dmy = dmy + str(cnt) + s[i]
						cnt = 1
			s = dmy
			dmy = ''
		return s


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		if n == 2:
			return '11'
		prev = '11'
		for i in range(2, n):
			count = 1
			temp = ''
			for i in range(len(prev) - 1):
				if prev[i] == prev[i + 1]:
					count += 1
				else:
					temp += str(count) + prev[i]
					count = 1
			if prev[i] == prev[i + 1]:
				temp += str(count) + prev[i]
			else:
				temp += '1' + prev[i + 1]
			prev = temp
		return prev


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		elif n == 2:
			return '11'
		s = '11'
		for i in range(n - 2):
			j = 0
			count = 1
			new = ''
			while j < len(s) - 1:
				if s[j] == s[j + 1]:
					count += 1
				else:
					new += str(count) + s[j]
					count = 1
				j += 1
			else:
				new += str(count) + s[j]
				s = new
		return s


class Solution:

	def lookandsay(self, n):

		def helper(n, s):
			if n == 1:
				return s
			i = 0
			length = len(s)
			res = ''
			while i < length:
				j = i
				while i < length and s[i] == s[j]:
					i += 1
				res += str(i - j) + s[j]
			return helper(n - 1, res)
		return helper(n, '1')


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		res = ''
		s = self.lookandsay(n - 1)
		frequency = 0
		for i in range(len(s)):
			frequency += 1
			if i == len(s) - 1 or s[i] != s[i + 1]:
				res = res + str(frequency) + s[i]
				frequency = 0
		return res


class Solution:

	def lookandsay(self, n):
		step = n
		n = '1'
		for i in range(step - 1):
			count = 0
			flag = 0
			next = str(n[flag])
			newNum = ''
			for item in n:
				if next == item:
					count += 1
				elif count > 0 and next != item:
					newNum += str(count) + next
					flag += count
					next = str(n[flag])
					count = 1
			n = newNum + str(count) + next
		return n


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		elif n == 2:
			return '11'
		val = '11'
		r = val[0]
		for i in range(n - 2):
			r = val[0]
			ans = ''
			c = 0
			for j in val:
				if j == r:
					c += 1
				else:
					ans += str(c) + r
					r = j
					c = 1
			ans += str(c) + r
			val = ans
		return ans


class Solution:

	def lookandsay(self, n):
		s = '1'
		for i in range(n - 1):
			s = self.res(s)
		return s

	def res(self, s):
		result = []
		i = 0
		while i < len(s):
			count = 1
			while i + 1 < len(s) and s[i] == s[i + 1]:
				i += 1
				count += 1
			result.append(str(count) + s[i])
			i += 1
		return ''.join(result)


class Solution:

	@staticmethod
	def lookandsay(n):
		if n <= 0:
			raise ValueError('n must be a positive integer.')
		if n == 1:
			return '1'
		prev_term = '1'
		for _ in range(2, n + 1):
			next_term = ''
			count = 1
			for i in range(1, len(prev_term)):
				if prev_term[i] == prev_term[i - 1]:
					count += 1
				else:
					next_term += str(count) + prev_term[i - 1]
					count = 1
			next_term += str(count) + prev_term[-1]
			prev_term = next_term
		return prev_term


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'

		def helper(n):
			(num, freq) = (None, None)
			s = ''
			for c in n:
				if num is None:
					num = c
					freq = 1
				elif c == num:
					freq += 1
				else:
					s += str(freq) + str(num)
					num = c
					freq = 1
			return s + str(freq) + str(num)
		tmp = '1'
		for i in range(0, n - 1):
			tmp = helper(tmp)
		return tmp


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 11
		s = '11'
		for i in range(3, n + 1):
			curr = ''
			s = s + '*'
			c = 1
			for j in range(1, len(s)):
				if s[j] != s[j - 1]:
					curr = curr + str(c)
					curr = curr + s[j - 1]
					c = 1
				else:
					c += 1
			s = curr
		return s


class Solution:

	def lookandsay(self, n):
		start = '1'
		count = 1
		ans = ''
		if n == 1:
			return 1
		for i in range(1, n):
			if len(ans) > 0:
				start = ans
			ans = ''
			j = 0
			while j < len(start):
				cnt = 1
				while j + 1 < len(start) and start[j] == start[j + 1]:
					cnt += 1
					j += 1
				j += 1
				ans += str(cnt) + start[j - 1]
		return ans


class Solution:

	def lookandsay(self, m):
		num = 1
		numStr = str(num)
		if m == 1:
			return numStr
		numStr = '11'
		while m > 2:
			i = 1
			n = len(numStr)
			res = ''
			while i < n:
				cou = 1
				while i < n and numStr[i] == numStr[i - 1]:
					i += 1
					cou += 1
				res += str(cou)
				res += str(numStr[i - 1])
				i += 1
			if numStr[n - 1] != numStr[n - 2]:
				res += '1'
				res += numStr[n - 1]
			numStr = res
			m -= 1
		return numStr


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		s = '1'
		for i in range(n - 1):
			(previous, count) = (s[0], 0)
			new = ''
			for current in s:
				if previous != current:
					new += str(count) + previous
					(previous, count) = (current, 1)
				else:
					count += 1
			new += str(count) + previous
			s = new
		return s


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		string = self.lookandsay(n - 1)
		m = len(string)
		i = 0
		ans = ''
		while i < m:
			count = 0
			curr = string[i]
			while i < m and curr == string[i]:
				count += 1
				i += 1
			ans = ans + str(count) + curr
		return ans


class Solution:

	def lookandsay(self, n):
		s = '1'
		ss = ''
		for i in range(n - 1):
			if len(s) == 1:
				s = '11'
				continue
			for j in range(len(s)):
				if j == 0:
					p = s[j]
					c = 1
				elif p == s[j]:
					c += 1
				else:
					ss = ss + str(c) + p
					p = s[j]
					c = 1
			ss = ss + str(c) + p
			s = ss
			ss = ''
		return s


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		prev = '1'
		for i in range(2, n + 1):
			curr = ''
			count = 1
			for j in range(1, len(prev)):
				if prev[j] == prev[j - 1]:
					count += 1
				else:
					curr += str(count) + prev[j - 1]
					count = 1
			curr += str(count) + prev[-1]
			prev = curr
		return prev


class Solution:

	def lookandsay(self, n):
		ans = '1'
		for i in range(1, n):
			last_str = ans
			l = len(ans)
			j = 0
			ans = ''
			while j < l:
				count = j
				try:
					while j < l and last_str[j] == last_str[count]:
						count += 1
				except:
					pass
				ans += str(count - j) + last_str[j]
				j = count
		return ans


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		s = '1'
		for i in range(2, n + 1):
			s += '#'
			l = len(s)
			temp = ''
			cnt = 1
			for j in range(1, l):
				if s[j] != s[j - 1]:
					temp += str(cnt)
					temp += s[j - 1]
					cnt = 1
				else:
					cnt += 1
			s = temp
		return s


class Solution:

	def value(self, val1):
		val1 = str(val1)
		v1 = val1[0]
		count = 1
		res = ''
		i = 1
		while i < len(val1):
			if i == len(val1) - 1 and val1[i] == v1:
				count += 1
				res += str(count) + v1
				i += 1
			elif val1[i] == v1:
				count += 1
				i += 1
			else:
				res += str(count) + v1
				v1 = val1[i]
				count = 0
		return int(res)

	def lookandsay(self, n):
		val = [1, 11, 21, 1211, 111221]
		for i in range(5, 30):
			val1 = val[i - 1]
			val2 = self.value(val1)
			val.append(val2)
		return val[n - 1]


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		if n == 2:
			return '11'
		s = '11'
		for i in range(2, n):
			count = 1
			new_str = ''
			for j in range(len(s)):
				if j == len(s) - 1:
					new_str = new_str + str(count) + s[j]
					break
				if s[j] == s[j + 1]:
					count += 1
				else:
					new_str = new_str + str(count) + s[j]
					count = 1
			s = new_str
		return new_str


class Solution:

	def lookandsay(self, n):
		res = '1'
		for i in range(n - 1):
			res = self.generator(res)
		return res

	def generator(self, res):
		ans = ''
		tempcount = {}
		checked = []
		for i in range(len(res)):
			if i < len(res) - 1 and res[i] == res[i + 1]:
				if res[i] in tempcount.keys():
					tempcount[res[i]] += 1
				else:
					tempcount[res[i]] = 1
			else:
				if res[i] in tempcount.keys():
					tempcount[res[i]] += 1
				else:
					tempcount[res[i]] = 1
				ans += str(tempcount[res[i]])
				ans += str(res[i])
				tempcount = {}
		return ans


class Solution:

	def lookandsay(self, n):
		i = 1
		cnt = 0
		temp = ''
		j = 0
		val_chk = []
		a = ['1', '11']
		if n < len(a):
			return a[n - 1]
		while i < n:
			x = a[i]
			while j < len(x):
				j = int(j)
				cnt = self.get(x, j)
				t = str(cnt)
				z = t + x[j]
				temp += z
				if cnt > 1:
					j = j + cnt - 1
				j += 1
			a.append(temp)
			val_chk = []
			cnt = 0
			z = ''
			i += 1
			temp = ''
			j = 0
		return a[n - 1]

	def get(self, x, j):
		cnt = 1
		l = len(x)
		while j < l - 1 and x[j] == x[j + 1]:
			cnt += 1
			j += 1
		return cnt


class Solution:

	def lookandsay(self, n):
		x = '1'
		if n == 1:
			return 1
		x = '11'
		if n == 2:
			return x
		for i in range(n - 2):
			count = 1
			dup = x[0]
			y = ''
			for j in range(1, len(x)):
				if x[j] == dup:
					count += 1
				else:
					y = y + str(count) + dup
					dup = x[j]
					count = 1
			y = y + str(count) + dup
			x = y
		return x


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		prev = self.lookandsay(n - 1)
		res = ''
		c = 1
		dig = prev[0]
		for i in range(1, len(prev)):
			if prev[i] == dig:
				c += 1
			else:
				res += str(c) + dig
				c = 1
				dig = prev[i]
		res += str(c) + dig
		return res


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		prev = self.lookandsay(n - 1)
		res = ''
		cnt = 1
		for i in range(len(prev)):
			if i == len(prev) - 1 or prev[i] != prev[i + 1]:
				res += str(cnt) + prev[i]
				cnt = 1
			else:
				cnt += 1
		return res


class Solution:

	def lookandsay(self, n):
		strr1 = '1'
		for i in range(n - 1):
			val = strr1[0]
			cnt = 0
			strr = ''
			for i in strr1:
				if i == val:
					cnt += 1
				else:
					strr += str(cnt) + val
					val = i
					cnt = 1
			strr += str(cnt) + val
			strr1 = strr
		return strr1


class Solution:

	def lookandsay(self, n):
		string = '1'
		if n == 1:
			return string
		for i in range(1, n):
			in_str = ''
			count = 1
			for j in range(1, len(string)):
				if string[j] == string[j - 1]:
					count = count + 1
				else:
					in_str = in_str + str(count)
					in_str = in_str + string[j - 1]
					count = 1
			in_str = in_str + str(count) + string[len(string) - 1]
			string = in_str
		return string


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		else:
			j = '1 '
			for _ in range(1, n):
				(count, main_string) = (1, [])
				string_it = lambda x: ''.join([str(y) + str(z) for (y, z) in x])
				for i in range(len(j) - 1):
					now = j[i]
					nex = j[i + 1]
					if now == nex:
						count += 1
					else:
						main_string.append((count, now))
						count = 1
				val = string_it(main_string)
				j = str(val) + ' '
			return val


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return '1'
		if n == 2:
			return '11'
		prev = '11$'
		for i in range(3, n + 1):
			res = ''
			l = 1
			r = 1
			c = 1
			while r < len(prev):
				if prev[l - 1] == prev[r]:
					c += 1
				else:
					res = res + str(c) + prev[l - 1]
					l = r + 1
					c = 1
				r += 1
			prev = res + '$'
		return prev[:len(prev) - 1]


class Solution:

	def lookandsay(self, n):
		if n == 1:
			return 1

		def fun(n):
			n = list(n)
			n.append(0)
			r = ''
			c = 0
			i = 0
			while i < len(n) - 1:
				if n[i] == n[i + 1]:
					c += 1
				else:
					r += str(c + 1)
					r += n[i]
					c = 0
				i += 1
			return r
		t = fun(str(1))
		for i in range(1, n - 1):
			t = fun(t)
		return t