“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 72nd day of continuous clocking of the force button algorithm 🎈!
🚀 Algorithm 🚀

🌲 Determine the subsequence

Given the strings s and t, determine whether S is a subsequence of t.

A subsequence of strings is a new string formed by deleting some (or none) characters from the original string without changing the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not).

Example 1:

Enter: s ="abc", t = "ahbgdc"Output:true
Copy the code

Example 2:

Enter: s ="axc", t = "ahbgdc"Output:false
Copy the code

Tip:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • Both strings consist of lowercase characters only.

🌻 c # method

In a simple way, each character is iterated to see if it is the same as ~

Code:

public class Solution {
public int FirstUniqChar(string s) {

    int[] arr=new int[26];  // An array of 26 letters
    for(int i=0; i<s.Length; i++) { arr[s[i]-'a'] + =1;  / / a - 0 b - 1..................... The corresponding digit is +1
    }
    for(int i=0; i<s.Length; i++) {if(arr[s[i]-'a'] = =1)  // When the position is 1
        {
            returni; }}return - 1; }}Copy the code

The execution result

By execution time:84Ms, beat out all Java commits18.50% user memory consumption:36.4MB, beat out all Java commits28.50% of the userCopy the code

🌻Java method: Use hash table to store frequency

Thinking analytical

Code:

class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        returni == n; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits84.99% user memory consumption:36.2MB, beat out all Java commits97.44% of the userCopy the code

Complexity analysis

Time: O(n+m) Space: O(1 ) 
Copy the code

💬 summary

  • Today is the seventy-second day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!